树状数组区间修改

有时，我们要支持区间修改，区间查询。
线段树可以做到。
但是树状数组更好写。
1d的情况：
设\(b[i]=a[i]-a[i-1]\)
则\(a[i]=b[1]+...+b[i]\)
\(a[1]+...+a[l]=(b[1])+(b[1]+b[2])+....(b[1]+...+b[l])\)
\(a[1]+...+a[l]=l*b[1]+(l-1)*b[2]+......+b[l]=sum((l-i+1)*b[i])\)
如果我们维护\(b[i]\)的和，\((i-1)*b[i]\)的树状数组\(c,d\)，就能维护\(a\)的前缀和，就能知道\(a\)的区间和。
这样子看上去功能比线段树少。
但是如果我们要维护区间乘积
线段树打标记要永久化。需要预处理出一种长度标记的幂次才能正确更新答案。这样子十分麻烦。
然而在区间乘法时，两个树状数组乘的值都是一定的，可以logn处理出来。
在区间查询时，我们可以算出b2的逆元，b1的逆元*(x+1)次，这个都能在查询后完成。
这样子比线段树更方便。
代码：

void ad(int x,int y){
	for(int i=x;i<=n;i+=i&-i)
		b1[i]+=y,b2[i]+=x*y;
}
int q(int x){
	int r=0;
	for(int i=x;i;i-=i&-i)
		r+=(x+1)*b1[i]-b2[i];
	return r;
}

树状数组区间修改

原文：https://www.cnblogs.com/ctmlpfs/p/13645598.html