Submission

PPTTTTTTTTTTTTTTTTTT

Score: 10

User: real_MYdkn_not_fake_100

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

Language: cpp

Time: 0.202 second

Submitted On: 2024-11-11 09:08:28

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

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

void build(int node, int start, int end) {
    if (start == end) {
        segTree[node] = base[start];
    } else {
        int mid = (start + end) / 2;
        build(2 * node + 1, start, mid);
        build(2 * node + 2, mid + 1, end);
        segTree[node] = segTree[2 * node + 1] + segTree[2 * node + 2];
    }
}

void update(int node, int start, int end, int idx, int value) {
    if (start == end) {
        base[idx] = value;
        segTree[node] = value;
    } else {
        int mid = (start + end) / 2;
        if (start <= idx && idx <= mid) {
            update(2 * node + 1, start, mid, idx, value);
        } else {
            update(2 * node + 2, mid + 1, end, idx, value);
        }
        segTree[node] = segTree[2 * node + 1] + segTree[2 * node + 2];
    }
}

int query(int node, int start, int end, int L, int R) {
    if (R < start || end < L) {
        return 0;
    }
    if (L <= start && end <= R) {
        return segTree[node];
    }
    int mid = (start + end) / 2;
    int leftSum = query(2 * node + 1, start, mid, L, R);
    int rightSum = query(2 * node + 2, mid + 1, end, L, R);
    return leftSum + rightSum;
}

int main() {
    cin >> n;
    base.resize(n);
    segTree.resize(4 * n);

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

    build(0, 0, n - 1);

    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;
            update(0, 0, n - 1, idx, change_to);
        }

        int s, f;
        cin >> s >> f;
        cout << query(0, 0, n - 1, s, f) << "\n";
    }

    return 0;
}