fenwick tree
树状数组已经是时代的眼泪了
感觉随着各种版本的线段树出世, 连区间和时间上都跟树状数组差不多了, 而且就我个人而言, 线段树比树状数组更容易理解一些
但是毕竟树状数组码量要小, 简单也是优势
复杂度
可差分信息, 比如区间和, 是可以logn维护的, 哪怕是区间加和, 也可以用两个数组来维护
而不可差分信息， 比如区间max值, 只能(logn)^2来维护, 所幸(logn)^2并不大
不同的写法
有太多种不同的写法了
很多人写fenwick tree是拿lowbit写, 下标从1开始
然而我抄来的板子是从0开始的, 我也比较喜欢从0开始的数组
template <typename T>
class fenwick
{
public:
vector<T> fenw;
int n;
fenwick(int _n) : n(_n)
{
fenw.resize(n);
}
void modify(int x, T v)
{
while (x < n)
{
fenw[x] += v;
x |= (x + 1);
}
}
void get(int x)
{
T v{};
while (x >= 0)
{
v += fenw[x];
x = (x & (x + 1)) - 1;
}
return v;
}
};
如何理解树状数组
lowbit当然好理解, 每个vec[i]维护的是从i开始往前的lowbit位的数据
每次add的时候, 需要通过+lowbit找到自己的所有父(这里用类似线段树的方式表达了一下同样需要保存这份数据的区间)加上数据
而query(x)的时候, vec[x]保存了lowbit(x)个元素, x-lowbit指的是剩余需要求的元素数量, 来到vec[x-lowbit]继续求
而x|(x+1)其实是什么呢?
放几张图
第一张是lowbit函数作用在[1, 1025)上的函数图像
第二张是x|(x+1)作用在[0, 2048)上的函数图像
能看出什么规律来吗?
有点类似是吧
然后我要放一张(x|(x+1))-x作用在[0, 2048) 的图像
do you get it?
如果你把他们的值打印出来的话
你会发现, 他们在区间上每一位所管辖的位数就是一样的.
为什么呢? 还记得lowbit是如何跳区间的吗?
void add(int x, int z)
{
while (x <= n)
{
c[x] += z;
x += lowbit(x);
}
}
而第二种方法是如何跳区间的?
void modify(int x, T v)
{
while (x < n)
{
fenw[x] += v;
x |= (x + 1);
}
}
一切尽在不言中, 如果再说仔细一些的话, 这之间的区别只是位运算的一些技巧区别
arr1 = np.arange(0, 1000)
arr2 = np.arange(1, 1001)
def op4(x):
return (x|(x+1))+1
np.vectorize(op4)(arr1)
def op5(x):
return x+(x&(-x))
np.vectorize(op5)(arr2)
这俩矩阵的输出是一模一样的
另一个当然也是
用法
-
log(n)
在需要区间加和的时候, 一般是使用差分数组的思维, 只修改前后两个值, 这是2log(n)的复杂度
那查询呢?
维护两个数组即可 -
(log(n))^2
计算不可差分值的时候, 也就是(x&(x+1))-1跳到l左边的话, 就别跳了, 改成x-1, 这个区间合并的过程是logn的, 所以整体复杂度是(logn)^2