树状数组

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
//tr[]数组 为树状数组
int a[N], tr[N];
int n, m;
//返回末尾最后一个1和后面的0
int lowbit(int x) {
    return x & (-x);
}
//树状数组的+操作 将x位置上的数+上y
void add(int x, int y) {
    for (int i = x; i <= n; i += lowbit(i)) {
        tr[i] += y;
    }
}
//求和以 1到x区间的和
int get_sum(int x) {
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        res += tr[i];
    }
    return res;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        add(i, a[i]);
    }
    while (m--) {
        int k, x, y;
        cin >> k >> x >> y;
        if (k == 1) {
            add(x, y);
        }
        else if (k == 0) {
            cout << get_sum(y) - get_sum(x - 1) << endl;
        }
    }

    return 0;
}

线段树

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct tr {
    int l, r, sum;
    tr() {
        l = 0; r = 0; sum = 0;
    }
    tr(int a, int b, int c) {
        l = a; r = b; sum = c;
    }
}tre[4*N];
int n, m;
int a[N];
//pushup 求x这个节点的权值=左儿子的权值+右儿子的权值
int pushup(int x) {
    tre[x].sum = tre[2 * x].sum + tre[2 * x+1].sum;
}
//建立l ~ r 的线段树
void build(int x, int l, int r) {
    //如果l==r 说明这个区间已经不能再分(长度为1)
    //直接给它赋值
    if (l == r) {
        tre[x] = tr(l, r, a[r]);
    }
    else {
        //不是叶子节点 先给他的l r 当前l r
        tre[x] = tr(l, r,0);
        int mid = l + r >> 1;
        //递归分出 左边 右边
        build(2 * x, l, mid);
        build(2 * x + 1, mid + 1, r);
        //递归结束后回溯算出 每个父亲的区间和
        pushup(x);
    }
}
//查询函数 给定根节点 查询l~r这个子区间的和
int query(int x, int l, int r) {
    //如果序列完全包含这个子区间 则直接加上
    if (tre[x].l >= l && tre[x].r <= r)
        return tre[x].sum;
    int mid = tre[x].l + tre[x].r >> 1;
    int sum = 0;
    //不完全包含则递归找下去
    //如果和做儿子有关联 递归左边
    if (l <= mid)sum = query(2 * x, l, r);
    //如果和右边有关系 则递归右边
    if (r >= mid + 1)sum += query(2 * x + 1, l, r);
    return sum;
}
//修改操作
void modify(int x, int pos, int v) {
    //如果他是一个叶子节点
    //则直接加上这个值
    if (tre[x].l == tre[x].r)
        tre[x].sum += v;
    else {
        int mid = tre[x].l + tre[x].r >> 1;
        //如果这个数的位置在他的左边
        //递归修改他的左儿子等
        if (pos <= mid)
            modify(x * 2, pos, v);
        //如果这个数的位置在他的右边
        //递归修改他的右儿子等等
        else modify(x * 2 + 1, pos, v);
        pushup(x);
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
//建立线段树
    build(1, 1, n);
    while (m--) {
        int k,x,y;
        cin >> k >> x >> y;
        if (k == 0)
            //输入 根节点 区间左端点 区间右端点
            //求出[l,r]区间和
            cout << query(1, x, y) << endl;
            //输入根节点 位置 x 加上y
        else modify(1, x, y);
    }
    return 0;
}