Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- using namespace std;
- int arr[1000000], segm[4000000];
- void build(int s, int e, int idx){
- if(s==e){
- segm[idx] = arr[s];
- return;
- }
- int mid = (s+e)/2;
- build(s, mid, idx*2);
- build(mid+1, e, idx*2+1);
- segm[idx] = segm[idx*2] + segm[idx*2+1];
- }
- int queries(int s, int e, int qs, int qe, int idx){
- if(qs>=s && qe<=e){
- return segm[idx];
- }
- else if(qs>e || qe < s){
- return 0;
- }
- int mid = (s+e)/2;
- int p1 = queries(s, mid, qs, qe, idx*2);
- int p2 = queries(mid+1, e, qs, qe, idx*2+1);
- return p1+p2;
- }
- void update(int s, int e, int us, int ue,int k,int idx){
- if(s==e && (us <= s && ue >= e)){
- segm[idx] = k;
- arr[s]+=k;
- return;
- }
- else if(ue < s || us > e){
- return;
- }
- int mid = (s+e)/2;
- update(s, mid, us, ue, k, idx*2);
- update(mid+1, e, us, ue, k, idx*2+1);
- segm[idx] = segm[idx*2]+segm[idx*2+1];
- }
- int main(){
- int N,Q,qS,qE,a,K, u;
- cin >> N >> Q;
- for(int i = 0; i<N; i++){
- cin >> arr[i];
- }
- build(0, N-1, 1);
- for(int i = 0; i<Q; i++){
- cin >> a;
- if(a == 2){
- cin >> qS >> qE;
- cout << queries(0, N-1, qS, qE, 1) << endl;
- }
- else{
- cin >> K >> u;
- update(0, N-1, K, K, u, 1);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement