• API
• FAQ
• Tools
• Archive
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.

Top