树状数组
简介¶
树状数组和下面的线段树可是亲兄弟了,但他俩毕竟还有一些区别:
树状数组能有的操作,线段树一定有;
线段树有的操作,树状数组不一定有。
这么看来选择线段树不就 「得天下了」 ?
事实上,树状数组的代码要比线段树短得多,思维也更清晰,在解决一些单点修改的问题时,树状数组是不二之选。
原理¶
如果要具体了解树状数组的工作原理,请看下面这张图:
这个结构的思想和线段树有些类似:用一个大节点表示一些小节点的信息,进行查询的时候只需要查询一些大节点而不是更多的小节点。
最下面的八个方块就代表存入
他们上面的参差不齐的剩下的方块就代表
很显然看出:
所以,如果你要算区间和的话,比如说要算
那么这种类似于跳一跳的连续跳到中心点而分值不断变大的原理是一样的(倍增)。
你从
用法及操作¶
那么问题来了,你是怎么知道 lowbit
:
1 2 3 4 | int lowbit(int x) {
// 算出x二进制的从右往左出现第一个1以及这个1之后的那些0组成数的二进制对应的十进制的数
return x & -x;
}
|
lowbit
的意思注释说明了,咱们就用这个说法来证明一下
发现第一个
这就是 lowbit
的用处,仅此而已(但也相当有用)。
你可能又问了:x & -x 是什么意思啊?
在一般情况下,对于 int 型的正数,最高位是 0,接下来是其二进制表示;而对于负数 (-x),表示方法是把 x 按位取反之后再加上 1。
例如 :
那么对于 单点修改 就更轻松了:
1 2 3 4 5 6 | void add(int x, int k) {
while (x <= n) { // 不能越界
c[x] = c[x] + k;
x = x + lowbit(x);
}
}
|
每次只要在他的上级那里更新就行,自己就可以不用管了。
1 2 3 4 5 6 7 8 | int getsum(int x) { // a[1]……a[x]的和
int ans = 0;
while (x >= 1) {
ans = ans + c[x];
x = x - lowbit(x);
}
return ans;
}
|
区间加 & 区间求和¶
若维护序列
进行推导
区间和可以用两个前缀和相减得到,因此只需要用两个树状数组分别维护
代码如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | int t1[MAXN], t2[MAXN], n;
inline int lowbit(int x) { return x & (-x); }
void add(int k, int v) {
int v1 = k * v;
while (k <= n) {
t1[k] += v, t2[k] += v1;
k += lowbit(k);
}
}
int getsum(int *t, int k) {
int ret = 0;
while (k) {
ret += t[k];
k -= lowbit(k);
}
return ret;
}
void add1(int l, int r, int v) {
add(l, v), add(r + 1, -v); // 将区间加差分为两个前缀加
}
long long getsum1(int l, int r) {
return (r + 1ll) * getsum(t1, r) - 1ll * l * getsum(t1, l - 1) -
(getsum(t2, r) - getsum(t2, l - 1));
}
|
Tricks¶
每一个节点的值是由所有与自己直接相连的儿子的值求和得到的。因此可以倒着考虑贡献,即每次确定完儿子的值后,用自己的值更新自己的直接父亲。
1 2 3 4 5 6 7 8 | // O(n)建树
void init() {
for (int i = 1; i <= n; ++i) {
t[i] += a[i];
int j = i + lowbit(i);
if (j <= n) t[j] += t[i];
}
}
|
参考 "可持久化线段树" 章节中,关于求区间第
因此可以想到算法:如果已经找到
- 求出
depth=\left \lfloor \log_2n \right \rfloor - 计算
t=\sum_{i=x+1}^{x+2^{depth}}a_i - 如果
sum+t \le k 2^{depth} x x - 将
depth depth
1 2 3 4 5 6 7 8 9 10 11 12 | //权值树状数组查询第k小
int kth(int k) {
int cnt = 0, ret = 0;
for (int i = log2(n); ~i; --i) { // i与上文depth含义相同
ret += 1 << i; // 尝试扩展
if (ret >= n || cnt + t[ret] >= k) // 如果扩展失败
ret -= 1 << i;
else
cnt += t[ret]; // 扩展成功后 要更新之前求和的值
}
return ret + 1;
}
|
时间戳优化:
对付多组数据很常见的技巧。如果每次输入新数据时,都暴力清空树状数组,就可能会造成超时。因此使用
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | //时间戳优化
int tag[MAXN], t[MAXN], Tag;
void reset() { ++Tag; }
void add(int k, int v) {
while (k <= n) {
if (tag[k] != Tag) t[k] = 0;
t[k] += v, tag[k] = Tag;
k += lowbit(k);
}
}
int getsum(int k) {
int ret = 0;
while (k) {
if (tag[k] == Tag) ret += t[k];
k -= lowbit(k);
}
return ret;
}
|
例题¶
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:HeRaNO, Zhoier, Ir1d, Xeonacid, wangdehu, ouuan, ranwen, ananbaobeichicun, Ycrpro
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用