「数据结构」树状数组

树状数组($Binary\ Indexed\ Trees$)是一个维护__前缀和__的数据结构,需要支持以下操作

  • $Add\ x\ y$,单点增加,a[x] += y
  • $Query\ x$,查询前缀和

前置知识

$lowbit$运算

$lowbit(n)$表示非负整数$n$在二进制表示下__最低位的1及其后边所有的0构成的数值__

为了实现$lowbit$运算,先把$n$取反,此时第$k$位变为$0$(设第$k$位是$1$,其后均为$0$),第$0\sim k-1$位变为$1$,再整体加一,所以第$k$位变为$1$,其后为$0$,其前每位恰好与原数相反,再按位求与($&$)即可得到。由于在补码下,$\sim n=-1-n$,所以

$$lowbit(n)=n\ &\ (\sim n+1)=n\ &\ -n$$

1
int lowbit(int n) { return n & -n; }

算法实现

对于一个原序列$a[]$,可以建立一个数组$tree[]$,来保存$a$的区间$[x-lowbit(x)+1, x]$内值的和,即

$$tree[x] = \sum_{i=x-lowbit(x)+1}^x{a[i]}$$

同时$tree$数组可以看成一个树形结构,并满足以下性质

  • 每个节点$tree[x]$保存以$x$为根的子树中所有叶节点的和
  • 每个节点$tree[x]$的子节点个数等于$lowbit(x)$的位数
  • 除树根外,每个节点$tree[x]$的父亲节点为$tree[x+lowbit(x)]$
  • 树的深度为$\log_2n$

根据这些性质,就很容易地写出代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct BIT {
int tree[maxn], n, m;
int lowbit(int k) { return k & -k; }
void add(int x, int k) {
for (; x <= maxn; x += x & -x) tree[x] += y;
}
int query(int x) {
int ans = 0;
for (; x; x -= x & -x) ans += tree[x];
return ans;
}
int init() {
for (int i = 1; i <= n; ++i) {
add(i, a[i]);
}
}
};

实际上,树状数组可以嵌套维护,来解决更多问题,例如区间修改

$Luogu$模板题目

Luogu P3374 树状数组1 (单点修改,区间查询)

Luogu P3368 树状数组2 (区间修改,单点查询)

Luogu P3372 线段树1 (区间修改,区间查询)

「数据结构」树状数组

https://blog.tonycrane.cc/p/8c13697e.html

作者

TonyCrane

发布于

2019-06-09

更新于

2020-05-05

许可协议