fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. vector <long long int> tree,a,lazy;
  4.  
  5. void build_tree(long long int node,long long int s,long long int e)
  6. {
  7.     if(s==e)
  8.     {
  9.         tree[node]=a[s];
  10.     }
  11.     else
  12.     {
  13.         long long int m=(s+e)/2;
  14.         build_tree(node*2,s,m);
  15.         build_tree(node*2+1,m+1,e);
  16.         tree[node]=tree[node*2]+tree[node*2+1];
  17.     }
  18. }
  19.  
  20. void update_tree(long long int node,long long int s,long long int e,long long int l,long long int r,long long int v)
  21. {
  22.     if(s==e)
  23.     {
  24.         tree[node]+=v;
  25.         return;
  26.     }
  27.     else if(s>r||e<l||s>e)
  28.         return;
  29.     else
  30.     {
  31.         long long int m=(s+e)/2;
  32.         update_tree(node*2,s,m,l,r,v);
  33.         update_tree(node*2+1,m+1,e,l,r,v);
  34.         //tree[node]=tree[node*2]+tree[node*2+1]; 
  35.         tree[node]+=v*(min(e,r)-max(s,l)+1);
  36.         //node*2 and node*2+1 are yet to be fully computed
  37.     }
  38. }
  39.  
  40. long long int query_tree(long long int node,long long int s,long long int e,long long int l,long long int r)
  41. {
  42.     if(r<s||e<l||s>e)
  43.         return 0;
  44.     if(l<=s&&e<=r)
  45.         return tree[node];
  46.     else
  47.     {
  48.         long long int m,p1,p2;
  49.         m=(s+e)/2;
  50.         p1=query_tree(node*2,s,m,l,r);
  51.         p2=query_tree(node*2+1,m+1,e,l,r);
  52.         return p1+p2;
  53.     }
  54. }
  55.  
  56. int main()
  57. {
  58.     ios_base :: sync_with_stdio(false);
  59.     cin.tie(NULL);
  60.     long long int t;
  61.     cin>>t;
  62.     while(t--)
  63.     {
  64.         long long int n,q;
  65.         cin>>n>>q;
  66.         a.resize(n,0);
  67.         tree.resize(4*n+1,0);
  68.         //lazy.resize(4*n,0);
  69.         build_tree(1,0,n-1);
  70.         while(q--)
  71.         {
  72.             long long int x;
  73.             cin>>x;
  74.             if(x==0)
  75.             {
  76.                 long long int l,r,v;
  77.                 cin>>l>>r>>v;
  78.                 update_tree(1,0,n-1,l-1,r-1,v);
  79.             }
  80.             else
  81.             {
  82.                 long long int l,r;
  83.                 cin>>l>>r;
  84.                 long long int res;
  85.                 res=query_tree(1,0,n-1,l-1,r-1);
  86.                 cout<<res<<"\n";
  87.             }
  88.         }
  89.         a.clear();
  90.         tree.clear();
  91.         //lazy.clear();
  92.     }
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0s 4308KB
comments (?)
stdin
copy 
1
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8 
0 5 7 14
1 4 8
stdout
copy 
80
508
https://ideone.com/9zpbb8
language:
C++ 4.3.2 (gcc-4.3.2)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!