线段树递归版本：

#include <bits/stdc++.h>
using namespace std;

int n, q;
int a[1000005];       // 原始数组，1-based
int st[4000005];      // 线段树数组

// build: 在节点 p 表示区间 [l,r] 上构建线段树
void build(int p, int l, int r) {
    if (l == r) {
        st[p] = a[l];  // 叶子节点直接存值
        return;
    }
    int m = (l + r) >> 1;
    build(p<<1,    l,   m);  // 构建左子树
    build(p<<1|1,  m+1, r);  // 构建右子树
    st[p] = st[p<<1] + st[p<<1|1];  // 父节点存左右和
}

// up: 单点更新，在位置 i 上加 v，p 表示当前节点区间 [l,r]
void up(int p, int l, int r, int i, int v) {
    if (l == r) {
        st[p] += v;  // 找到叶子，累加 v
        return;
    }
    int m = (l + r) >> 1;
    if (i <= m) {
        up(p<<1,    l,   m, i, v);  // 更新左子树
    } else {
        up(p<<1|1,  m+1, r, i, v);  // 更新右子树
    }
    st[p] = st[p<<1] + st[p<<1|1];  // 回溯时重算父节点
}

// qr: 区间查询，返回区间 [L,R] 的和，p 表示当前节点区间 [l,r]
int qr(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) {
        return st[p];  // 当前区间完全包含在查询区间内
    }
    int m = (l + r) >> 1, res = 0;
    if (L <= m) res += qr(p<<1,    l,   m, L, R);  // 查询左子树
    if (R >  m) res += qr(p<<1|1,  m+1, r, L, R);  // 查询右子树
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];  // 读入初始数组
    }

    build(1, 1, n);  // 构建线段树

    while (q--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            // 类型1：单点加 x，把 a[x] 加上 y
            up(1, 1, n, x, y);
        } else {
            // 类型2：区间查询 [x,y] 的和
            int ans = qr(1, 1, n, x, y);
            cout << ans << "\n";
        }
    }
    return 0;
}

线段树非递归版：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAX = 1 << 21; // 足够大的数组大小，满足最大节点数（2^20=1048576）
int n, q, M; // n:数组大小, q:操作数, M:叶子节点起始索引
LL tr[MAX];   // 线段树数组
// 建树函数：自底向上构建线段树
void build() {
    // 从最后一个非叶节点开始向上计算父节点值
    for (int i = M-1; i; i--) 
        tr[i] = tr[i<<1] + tr[i<<1|1];
}
// 更新函数：位置i增加x
void upd(int i, LL x) {
    // 定位到叶子节点位置
    i = M + i - 1; 
    tr[i] += x; // 更新叶子节点值
    // 从叶子节点向上更新所有父节点
    while (i > 1) {
        i >>= 1; // 移动到父节点
        tr[i] = tr[i<<1] + tr[i<<1|1]; // 用左右儿子更新父节点
    }
}

// 查询函数：求[l,r]区间和
LL qry(int l, int r) {
    LL res = 0; // 结果变量
    // 定位到叶子节点位置
    l = l + M - 1;
    r = r + M - 1;
    // 左右指针相向移动计算区间和
    while (l <= r) {
        // 左指针是右孩子时计入
        if (l & 1) res += tr[l++];
        // 右指针是左孩子时计入
        if (!(r & 1)) res += tr[r--];
        // 移动到上一层节点
        l >>= 1;
        r >>= 1;
    }
    return res;
}

int main() {
    // 读入n和q
    scanf("%d%d", &n, &q);
    // 计算M（大于n的最小二次幂）
    M = 1;
    while (M <= n) M <<= 1;
    // 初始化线段树数组为0
    memset(tr, 0, sizeof(tr));
    // 读入初始数组存入叶子节点
    for (int i = 1; i <= n; i++) 
        scanf("%lld", &tr[M + i - 1]);
    // 构建线段树
    build();
    
    // 处理每个操作
    while (q--) {
        int op, x, y;
        scanf("%d", &op);
        if (op == 1) { 
            // 更新操作：位置x增加y
            scanf("%d%d", &x, &y);
            upd(x, y);
        } else { 
            // 查询操作：区间[x,y]的和
            scanf("%d%d", &x, &y);
            printf("%lld\n", qry(x, y));
        }
    }
    return 0;
}

树状数组

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
long long arr[N];
long long tree[N];
int n;
int q;
inline int lowbit(int x) {
    return x & (-x);
}
long long prefix(int idx) {
    long long res = 0;

    while (idx) {
        res += tree[idx];
        idx -= lowbit(idx);
    }

    return res;
}

long long query(int l, int r) {
    return prefix(r) - prefix(l - 1);
}

void update(int idx, int value) {
    arr[idx] += value;

    while (idx <= n) {
        tree[idx] += value;
        idx += lowbit(idx);
    }
}

int main() {
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        int tmp;
        cin >> tmp;
        update(i, tmp);
    }
    for (int j = 0; j < q; j++) {
        int op;
        cin >> op;

        if (op == 1) {
            int i, x;
            cin >> i >> x;
            update(i, x);
        } else if (op == 2) {
            int l, r;
            cin >> l >> r;
            cout << query(l, r) << endl;
        }
    }

    return 0;
}