1 条题解

  • 0
    @ 2025-10-14 9:18:33
    #include <bits/stdc++.h>
    using namespace std;
    using ll = long long;
    int n, q;
    ll t[500020];
    ll l[500020];
    ll r[500020];
    ll m[500020];
    void build(int idx, int lt, int rt) {
        l[idx] = lt;
        r[idx] = rt;
        m[idx] = (lt + rt) / 2;
        if (lt < rt) {
            build(idx << 1, lt, m[idx]);
            build(idx << 1 | 1, m[idx] + 1, rt);
        }
        return;
    }
    void add(int idx, int u, ll v) {
        if (l[idx] == r[idx]) {
            t[idx] += v;
            return;
        }
        if (m[idx] >= u) {
            add(idx << 1, u, v);
        } else {
            add(idx << 1 | 1, u, v);
        }
        t[idx] = t[idx << 1] + t[idx << 1 | 1];
        return;
    }
    ll query(int idx, int ql, int qr) {
        if (ql <= l[idx] && qr >= r[idx]) {
            return t[idx];
        }
        ll sum = 0;
        if (m[idx] >= ql) {
            sum += query(idx << 1, ql, qr);
        }
        if (m[idx] < qr) {
            sum += query(idx << 1 | 1, ql, qr);
        }
        return sum;
    }
    int main() {
        cin >> n >> q;
        build(1, 1, n);
        for (int i = 0; i < q; i++) {
            int flag = 0;
            cin >> flag;
            if (flag == 0) {
                int a;
                ll b;
                cin >> a >> b;
                add(1, a, b);
            } else {
                int a, b;
                cin >> a >> b;
                cout << query(1, a, b) << endl;
            }
        }
        return 0;
    }
    
    • 1

    信息

    ID
    1266
    时间
    1000ms
    内存
    256MiB
    难度
    (无)
    标签
    (无)
    递交数
    0
    已通过
    0
    上传者