SHARE
TWEET

Segment tree

FEgor04 Sep 16th, 2019 93 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. vector<ll> a;
  5. vector<ll> t;
  6.  
  7. void build(int v, ll l, ll r) {
  8.     if(r-l==1) {
  9.         t[v] = a[l];
  10.         return;
  11.     }
  12.     ll mid = l + (r-l)/2;
  13.     build(2*v, l, mid);
  14.     build(2*v+1, mid, r);                                                
  15.     t[v] = t[2*v] + t[2*v+1];
  16.     //cerr << v << " " << l << " " << r << endl;
  17.     //printf("t[%d] = %d\n", v, t[v]);
  18. }
  19.  
  20. ll get(int v, int l,int r,int ql,int qr) {
  21.     if(ql <= l && r <= qr) {
  22.         return t[v];
  23.     }
  24.     if(r <= ql || qr <= l) {   
  25.         return 0;
  26.     }
  27.     ll mid = l + (r-l)/2;
  28.     ll ansl = get(2*v, l, mid, ql,qr);
  29.     ll ansr = get(2*v+1, mid, r, ql, qr);
  30.     return ansr+ansl;
  31. }
  32.  
  33. void update(int v, int l, int r, int k, ll x) {
  34.     //cout << "V: " << v << " k == " << k << " x == " << x << "l == " << l << " r == " << r << "\n";
  35.     if(r-l==1) {
  36.         t[v]+=x;
  37.         return;
  38.     }
  39.     ll mid = l+(r-l)/2;
  40.     if(k < mid) {
  41.         update(2*v, l, mid, k, x);
  42.     }
  43.     else {
  44.         update(2*v+1, mid, r, k, x);
  45.     }
  46.     t[v] = t[2*v] + t[2*v+1];
  47. //
  48. }
  49.  
  50. int main() {
  51.     ios_base::sync_with_stdio(false);
  52.     cin.tie(NULL);
  53.     freopen("rsq2.in", "r", stdin);
  54.     freopen("rsq2.out", "w", stdout);
  55.     ll n, m, p1, p2, type;
  56.     cin >> n >> m;
  57.     a.resize(n+1);
  58.     t.resize(4*n);
  59.     for(int i = 1; i<=n; i++) {
  60.         cin >> a[i];
  61.     }
  62.     build(1, 1, n+1);
  63.     for(int i = 0; i < m; i++) {
  64.         cin >> type >> p1 >> p2;
  65.         if(type == 2) {
  66.             //cout << "";
  67.             cout << get(1, 1, n+1, p1, p2+1) << '\n';
  68.         }
  69.         else {
  70.             //cout << p1+a.size()+1 << "\n\n" <<  << "\n\n\n";
  71.            
  72.             update(1, 1, n+1, p1, p2);
  73.             //for(int j = 1; j <= n*2; j++) {
  74.             //  cout << t[j] << " ";
  75.             //}
  76.             //cout << endl << endl;
  77.         }
  78.     }
  79.    
  80.     return 0;
  81. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top