查看“︁13-高级数据结构/01-树状数组”︁的源代码


== 树状数组（Fenwick Tree / BIT） ==

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

=== 核心操作 ===

<code>lowbit(x) = x & -x</code>，取出 <math>x</math> 在二进制下最低位的 <math>1</math> 及其后面的 <math>0</math>。

<syntaxhighlight lang="cpp">
int lowbit(int x)
{
    return x & -x;
}
</syntaxhighlight>

=== 基础模板 ===

<syntaxhighlight lang="cpp">
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);
}
</syntaxhighlight>

== 应用场景 ==

=== 1. 维护权值数组 ===

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

<syntaxhighlight lang="cpp">
// 统计 <= x 的元素个数
int cnt = sum(x);

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

=== 2. 求逆序对 ===

<syntaxhighlight lang="cpp">
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;
}
</syntaxhighlight>

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

<syntaxhighlight lang="cpp">
// 区间 [l, r] + k
add(l, k);
add(r + 1, -k);

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

== 二维树状数组 ==

<syntaxhighlight lang="cpp">
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);
}
</syntaxhighlight>

[[Category:高级数据结构]]
[[Category:三三文档]]