33DAI：批量导入三三文档

2026-05-20T18:24:10Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 18:24的版本
第117行：		第117行：
	[[Category:高级数据结构]]		[[Category:高级数据结构]]
	[[Category:三三文档]]		[[Category:三三文档]]

33DAI：导入1个版本

2026-05-20T18:12:30Z

导入1个版本

←上一版本	2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

新页面

== 树状数组（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:三三文档]]

13-高级数据结构/01-树状数组 - 版本历史

33DAI：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档