刷题笔记
1. 树状数组维护区间的和、最值:
a) 维护区间的和还蛮简单的,就是记住 trees[x]保存的是 trees[x-lowbit(x)+1, x]的
和,然后更新的时候 while(x<=n)不断地给 trees[x]加上 k,然后用 x+=lowbit(x)
来找父节点即可。而查询区间前缀和是 while(x),不断地给 ans 加上 trees[x],
然后 x = x-lowbit(x)不断地找前继节点即可。可以康康模板代码里写的。查询
区间[l, r]内的和的时候用前缀和(r) – 前缀和(l)即可。
b) 维护区间的最值:
这个就比较复杂了,因为最值没有加和性。
对于树状数组不变(即没有单点修改,只有建立的过程),其 tadd 函数可以沿
用维护区间和的代码,只是每一次需要变为 trees[x] = max(trees[x], k)。而如果
是有单点修改的话,这样就是错的。试设想,如果你把一个本应该是某区间内
最大值的点修改成很小的 k,那么你用 trees[x] = max(trees[x], k)这样的赋值,
最大值根本就不会被修改,仍是 trees[x](因为它更大)。当然,如果你知道每
次修改都只会把 a[x]的值改大,你仍可以只用普通的 tadd()函数来更新(如最
长下降子序列这样的问题)。否则,单点修改变得很复杂:
我们只能记结论了,对于 x 这个点被修改,即我们首先手动修改了 a[x] = k,
然后调用 update(x)去更新树状数组的值。而 x 这点在没有 x += lowbit(x)之前,
只会影响到 x-1、x-2…. x-2^k 这些,其中
< lowbit(x)且
≥lowbit(x)。于
是我们可以写出下列更新函数:
void update(int x)
{
int lx, i;
while(x<=n)
{
trees[x] = a[x]; //之前已经手动更新好 a[x]了
lx = lowbit(x);
for(int i=1; i<lx; i<<=2)
trees[x] = max(trees[x], trees[x-i]);
x += lowbit(x);
}
}
这个算法复杂度是 O((nlogn)^2)其实也很少使用,树状数组更常用的是静态区
间的最值维护。
其中建立树状数组的方法和维护区间和一样,之后不再更新。而查询的时候不
能用前缀和相减,因为最大值没有区间可减性。仔细思考会发现,trees[x]储存
的是[x-lowbit(x)+1, x]中的最大值,因此我们在查询某一区间的最值时,只需
要能找到一种方法遍历那个区间就好了。设我们查询的是[x, y]区间,在查询
时当 y-lowbit(y) ≥x 的时 候 , trees[y]就 是 这一段 区 间的最值 , 即 ans =
max(trees[y], ans)而当这个条件不满足但 y 仍然大于等于 x 时,我们需要把 ans
设为 max(ans, a[y])然后继续用先前的条件更新 ans。于是可以写出以下代码:
int tsearch(int x, int y)