Submission

Score: 100

User: KantaponZ

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

Language: cpp

Time: 0.058 second

Submitted On: 2025-09-25 01:10:56

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

int N, Q;
int tree[1000001];
int A[1000001];

void upd(int idx, int val) {
    for (int i = idx; i <= N; i += (i & -i)) {
        tree[i] += (val - A[idx]);
    }
    A[idx] = val;
}

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

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int i = 1; i <= N; i++) {
        int x;
        cin >> x;
        upd(i, x);
    }
    cin >> Q;
    while (Q--) {
        int T;
        cin >> T;
        while (T--) {
            int x, y;
            cin >> x >> y;
            x++;
            upd(x, y);
        }
        int x, y; cin >> x >> y;
        x++; y++;
        cout << query(y) - query(x - 1) << "\n";
    }
}


/*
8
4 1 2 3 4 2 5 8
2
1
4 10
3 6
2
2 3
7 4
1 5

*/