15天大厂真题带刷 - ZT19 | 不用线段树，用树状数组

虽然题目标题写的线段树，但实际上更适合用树状数组求解。先上传一下代码，后续再试试线段树。

链接 - 树状数组详解

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

int n;
vector<long long> c;

int lowbit(int x) {
    return x & -x;
}

//计算a[1]至a[x]的和
long long getSum(int x) {
    long long ans = 0;
    while (x > 0) {
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

//a[x]单点修改，增加addNum。c数组相应的x和x的所有祖先都要增加addNum
void add(int x, int addNum) {
    while (x <= n) {
        c[x] += addNum;
        x += lowbit(x);
    }
}

int main() {
    int q, a;
    cin >> n >> q;
    c.resize(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> a;
        //后面三行代码可以用add(i, a)；代替，但是时间复杂度增加
        c[i] += a;
        int j = i + lowbit(i);
        if (j <= n) c[j] += c[i];
    }
    int op, l, r;
    while (q--) {
        cin >> op >> l >> r;
        if (op == 1) {
            add(l, r);
        } else {
            cout << getSum(r) - getSum(l - 1) << endl;
        }
    }
}