Submission

PPTTTTTTTTTTTTTTTTTT

Score: 10

User: real_MYdkn_not_fake_100

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

Language: cpp

Time: 0.200 second

Submitted On: 2024-11-11 09:11:03

#include <iostream>
#include <vector>
using namespace std;

vector<int> base, BIT;
int n, m;

void updateBIT(int idx, int diff) {
    while (idx < BIT.size()) {
        BIT[idx] += diff;
        idx += idx & -idx;
    }
}

int queryBIT(int idx) {
    int sum = 0;
    while (idx > 0) {
        sum += BIT[idx];
        idx -= idx & -idx;
    }
    return sum;
}

void buildBIT() {
    BIT.assign(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        updateBIT(i + 1, base[i]);
    }
}

int main() {
    cin >> n;
    base.resize(n);
    
    for (int i = 0; i < n; ++i) {
        cin >> base[i];
    }

    buildBIT();

    cin >> m;
    for (int i = 0; i < m; ++i) {
        int p;
        cin >> p;

        for (int j = 0; j < p; ++j) {
            int idx, change_to;
            cin >> idx >> change_to;
            int diff = change_to - base[idx];
            base[idx] = change_to;
            updateBIT(idx + 1, diff);  // Update the BIT with the difference
        }

        int s, f;
        cin >> s >> f;
        int result = queryBIT(f + 1) - queryBIT(s);
        cout << result << "\n";
    }

    return 0;
}