13-高级数据结构/01-树状数组

树状数组（Fenwick Tree / BIT）

树状数组用于高效维护前缀和，支持单点修改和区间查询，时间复杂度 [math]\displaystyle{ O(\log n) }[/math]。

核心操作

lowbit(x) = x & -x，取出 [math]\displaystyle{ x }[/math] 在二进制下最低位的 [math]\displaystyle{ 1 }[/math] 及其后面的 [math]\displaystyle{ 0 }[/math]。

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

基础模板

int bit[MAXN], n;

// 单点 a[i] += delta
void add(int i, int delta)
{
    for (; i <= n; i += lowbit(i))
        bit[i] += delta;
}

// 查询前缀和 sum[1..i]
int sum(int i)
{
    int res = 0;
    for (; i > 0; i -= lowbit(i))
        res += bit[i];
    return res;
}

// 区间和 [l, r]
int range_sum(int l, int r)
{
    return sum(r) - sum(l - 1);
}

应用场景

1. 维护权值数组

将值作为下标，快速统计区间内元素个数（结合离散化）：

// 统计 <= x 的元素个数
int cnt = sum(x);

// 插入一个元素
add(x, 1);

2. 求逆序对

long long inversion_count(vector<int>& a)
{
    // 先离散化
    Discrete disc(a);
    long long ans = 0;
    memset(bit, 0, sizeof bit);
    for (int i = 1; i <= n; i++)
    {
        int idx = disc.id(a[i]);
        ans += i - 1 - sum(idx); // 前面比 a[i] 大的数
        add(idx, 1);
    }
    return ans;
}

3. 维护差分数组（区间修改 + 单点查询）

// 区间 [l, r] + k
add(l, k);
add(r + 1, -k);

// 查询 a[x]（即差分数组的前缀和）
int val = sum(x);

二维树状数组

int bit[MAXN][MAXM];

void add(int x, int y, int delta)
{
    for (int i = x; i <= n; i += lowbit(i))
        for (int j = y; j <= m; j += lowbit(j))
            bit[i][j] += delta;
}

int sum(int x, int y)
{
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        for (int j = y; j > 0; j -= lowbit(j))
            res += bit[i][j];
    return res;
}

// 子矩阵 (x1,y1) 到 (x2,y2) 的和
int query(int x1, int y1, int x2, int y2)
{
    return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1);
}