树状数组（Binary Indexed Tree）是一种高效处理动态数组前缀和的数据结构，能够在O(log n)时间内完成单点修改和区间查询操作。根据应用场景的不同，树状数组主要分为两类基础模板：第一类支持单点修改与区间查询，第二类支持区间修改与单点查询。

模板一：单点修改 + 区间查询

该模板的核心思想是维护一个辅助数组，通过lowbit运算确定每个节点管理的区间范围。修改操作时，只需更新影响到的相关节点；查询前缀和时，将目标位置分解为多个管理区间的组合。

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

const int MAXN = 500010;
int N, M;
int BIT[MAXN];

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

void update(int index, int delta) {
    while (index <= N) {
        BIT[index] += delta;
        index += getLowbit(index);
    }
}

int query(int index) {
    int sum = 0;
    while (index > 0) {
        sum += BIT[index];
        index -= getLowbit(index);
    }
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) {
        int val;
        cin >> val;
        update(i, val);
    }
    
    for (int i = 0; i < M; ++i) {
        int op;
        cin >> op;
        if (op == 1) {
            int pos, delta;
            cin >> pos >> delta;
            update(pos, delta);
        } else {
            int l, r;
            cin >> l >> r;
            cout << query(r) - query(l - 1) << '\n';
        }
    }
    return 0;
}

模板二：区间修改 + 单点查询

区间修改的实现利用了差分数组的思想。通过在区间起始位置加delta，区间结束位置加1处减delta，可以将区间修改转化为两个单点修改。查询时，将原数组值与差分数组的前缀和相加即可得到当前位置的实际值。

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

const int MAXN = 500010;
int N, M;
int BIT[MAXN], arr[MAXN];

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

void update(int index, int delta) {
    while (index <= N) {
        BIT[index] += delta;
        index += getLowbit(index);
    }
}

int query(int index) {
    int sum = 0;
    while (index > 0) {
        sum += BIT[index];
        index -= getLowbit(index);
    }
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) {
        cin >> arr[i];
    }
    
    for (int i = 0; i < M; ++i) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r, delta;
            cin >> l >> r >> delta;
            update(l, delta);
            update(r + 1, -delta);
        } else {
            int pos;
            cin >> pos;
            cout << arr[pos] + query(pos) << '\n';
        }
    }
    return 0;
}

核心原理

树状数组的关键在于lowbit运算，它返回参数二进制表示中最低位的1所对应的值。每个树状数组节点管理从该位置向前lowbit长度个元素，通过这种分层结构，可以在logn时间内完成各种操作。

两种模板的区别仅在于应用场景的不同：第一种直接维护原数组的前缀和，第二种通过差分数组间接实现区间修改。理解差分数组与原数组的关系是掌握第二类模板的关键。