Created
August 13, 2019 17:45
-
-
Save lawrencefmm/b4d49cd6229d0e2b7c10d510434dc933 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
const int maxn = 1e5; | |
#define LEFT (2*node) | |
#define RIGHT ((2*node) + 1) | |
#define MID ((l + r)/2) | |
int tree[3*maxn], v[maxn]; | |
int op(int a, int b) | |
{ | |
return a + b; | |
} | |
void build(int node, int l, int r) | |
{ | |
if(l == r) tree[node] = v[l]; | |
else | |
{ | |
build(LEFT, l, MID); | |
build(RIGHT, MID + 1, r); | |
tree[node] = op(tree[LEFT], tree[RIGHT]); | |
} | |
} | |
int query(int node, int l, int r, int a, int b) | |
{ | |
if(a > r or b < l) return 0; | |
if(a <= l and r <= b) return tree[node]; | |
int q1 = query(LEFT, l, MID, a, b); | |
int q2 = query(RIGHT, MID + 1, r, a, b); | |
return q1 + q2; | |
} | |
void update(int node, int l, int r, int pos, int val) | |
{ | |
if(l == r) tree[node] = v[l] = val; | |
else | |
{ | |
if(pos <= MID) update(LEFT, l, MID, pos, val); | |
else update(RIGHT, MID + 1, r, pos, val); | |
tree[node] = op(tree[LEFT], tree[RIGHT]); | |
} | |
} | |
int main() | |
{ | |
int n, q; | |
cin >> n >> q; | |
for(int i = 1; i <= n; i++) | |
cin >> v[i]; | |
build(1, 1, n); | |
while(q--) | |
{ | |
int op, a, b; | |
cin >> op >> a >> b; | |
if(op == 0) | |
{ | |
cout << query(1, 1, n, a, b) << "\n"; | |
} | |
else | |
{ | |
update(1, 1, n, a, b); | |
for(int i = 1; i <= n; i++) | |
cout << v[i] << " \n"[i == n]; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Thank you!