Submission

PPPPPPPPPPPPPPPPPPPP

Score: 100

User: njoop

Problemset: ผลบวก (ยาก)

Language: cpp

Time: 0.079 second

Submitted On: 2024-11-30 22:34:57

#include <bits/stdc++.h>
using namespace std;

int n, q, c, id, va, l, r;
int fw[1000010];

void update(int idx, int val){
    for(int i = idx; i <= n; i += (i&-i)) fw[i] += val;
}

int query(int idx){
    int sum = 0;
    for(int i = idx; i > 0; i -= (i&-i)) sum += fw[i];
    return sum;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> va;
        update(i, va);
    }
    cin >> q;
    while(q--) {
        int t;
        cin >> t;
        while(t--) {
            cin >> id >> va;
            update(id+1, va-query(id+1)+query(id));
        }
        cin >> l >> r;
        cout << query(r+1) - query(l) << "\n";
    }
    return 0;
}