Submission

PPxxxxxxxxxxxxxxxxxx

Score: 10

User: chawinkn

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

Language: cpp

Time: 0.002 second

Submitted On: 2024-11-25 20:47:53

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

const int MAX_N = 1e5+9;
int n, tree[2*MAX_N];

int query(int l, int r) {
    int sum=0;
    for (l += n, r += n+1; l < r; l/=2, r/=2) {
        if (l&1) sum += tree[l++];
        if (r&1) sum += tree[--r];
    }
    return sum;
}

void update(int i, int v) {
    tree[i+=n] = v;
    for (i /= 2; i >= 1; i/=2) tree[i] = tree[2*i]+tree[2*i+1];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		update(i, a);
	}
	int q;
	cin >> q;
    while (q--) {
        int t, x, y;
		cin >> t;
		while (t--) {
			int i, j;
			cin >> i >> j;
			update(i, j);
		}
		cin >> x >> y;
		cout << query(x, y) << "\n";
    }
    return 0;
}