树状数组整理（2.区间修改、二维）-tutorial mysql-php.cn

树状数组整理（2.区间修改、二维）

WBOY

Lepaskan： 2016-06-07 15:10:02

asal

1390 orang telah melayarinya

1.区间整体加一个数，单点求：已经很常用的方法了，就当成有多少线段覆盖，对a[l,r]k的操作转化为对辅助数组b[l]k,b[r1]-k，树状数组维护b[i]前缀和就好…… 具体来说，是对a[i]差分后生成新数组b[i]，使得b[i]=a[i]-a[i-1]，这样成段修改时：对il或ir1，a

1.区间整体加一个数，单点求值：

已经很常用的方法了，就当成有多少线段覆盖，对a[l,r]+k的操作转化为对辅助数组b[l]+k,b[r+1]-k，树状数组维护b[i]前缀和就好……
具体来说，是对a[i]差分后生成新数组b[i]，使得b[i]=a[i]-a[i-1]，这样成段修改时：
对ir+1，a[i]值不变故b[i]不变；l 但b[l]'=(a[l]+k)-a[l-1]=b[l]+k；b[r+1]'=a[r+1]-(a[r]+k)=b[r+1]-k。
同时对b[i]求前缀和会发现：
sum(p)=b[1]+b[2]+...+b[p]=(a[1]-a[0])+(a[2]-a[1])+...+(b[p]-b[p-1])=a[p]-a[0]=a[p]
这样单点求值的方式也出来了，上代码（套用了下原始的BIT）：

struct BIT_ex {
  BIT t; void init(int s) {t.init(s);}
  void change(int l, int r, _int k) {t.change(l,k); t.change(r+1,-k);}
  _int get(int p) {return t.sum(p);}
};

Salin selepas log masuk

2.区间整体加一个数，求区间和（前缀和）：

好像不是很常见，普及推广一下……
区间整体的修改已经搞出来，肯定是要继续用结论了……
上面差分数组得出了sum(p)=a[p]，这里求前缀和当然是求a[0]+a[1]+...+a[p]了~剩下的全是算数
a[0]+a[1]+a[2]+a[3]+...+a[p]=0+sum(1)+sum(2)+sum(3)+...+a[p]=(b[1])+(b[1]+b[2])+(b[1]+b[2]+b[3])+...+(b[1]+...+b[p])
b[1]在sum(1..p)中都出现，共p次，b[2]在sum(2..p)出现(p-1)次，类推可得
原式=p*b[1]+(p-1)*b[2]+(p-2)*b[3]+...+1*b[p]
本来想把每一项当成一个整体用BIT搞，但发现对于不同的p值，每项也会跟着变，显然没办法……
这里看到前面系数和b[]的下标和都是(p+1)，考虑逆用倒序相加大法：
原式=(p+1)*(b[1]+b[2]+b[3]+...+b[p])-(1*b[1]+2*b[2]+3*b[3]+...+p*b[p])
前面括号里是直接对b[i]求的前缀和，后面括号是对i*b[i]求前缀和——系数和下标一致的项出来了！
好，这样我们可以搞两个BIT，一个是维护b[i]的前缀和，一个维护i*b[i]的前缀和，维护方法同上
为了减少依赖所以这里仍然套了原始BIT，套BIT_ex会更好写，上代码：

struct BIT_im {
  BIT t1; BIT t2; void init(int s) {t1.init(s); t2.init(s);}
  void chage(_int l, _int r, _int k) {
    t1.change(l,k); t1.change(r+1,-k);
    t2.change(l,l*k); t2.change(r+1,-(r+1)*k);
  }
  _int sum(_int p) {return (p+1)*t1.sum(p)-t2.sum(p);}
};

Salin selepas log masuk

3.二维（多维）树状数组：

一维是前缀和，sum(p)=sum{a[i],i 二维的话，sum(x,y)=sum{a[i][j],i 多维类似，只讨论二维
静态维护很简单：

for (int i=1; i
<p><span>这样如果求(x1,y1)-(x2,y2)构成的矩形和，ans=s[x2][y2]-s[x1-1][y2]-s[x2,y1-1]+s[x1-1][y1-1]<br>
那么动态维护呢？首先对(a[i])[]这个数组可以用BIT来维护一个前缀和，再维护维护(a[i])[]前缀和BIT的前缀和……好绕<br>
总之呢，可以先用一组BIT可以维护多条平行线上的和，再用一个和它们正交的BIT把它们挂进去维护，此时原来那组BIT的意义其实已经变了……<br>
这个思路比较像下面这段代码（鸣谢mlzmlz95）：</span></p>
<pre class="brush:php;toolbar:false">for(i=1;i
<p><span>那么上代码：</span></p>
<pre class="brush:php;toolbar:false">struct BIT_2D {
  BIT c[N]; int n;
  void init(int s1,int s2) {n=s1; while (s1) c[s1--].init(s2);}
  void change(int x,int y,int k) {for (; x
<p><span>这个实现中，我们通过外层BIT来确定里层BIT的更新，初始化要把它们循环一遍设定好尺寸<br>
至于3D，那就再挂个2D吧，不过求一个长方体和的公式有点复杂>_
那么想搞多维难道就要把前面所有维的写出来吗……太麻烦了，我们直接手工inline一下，再稍作修改：</span></p>
<pre class="brush:php;toolbar:false">struct BIT_2D_in {
  int c[N][M],n,m;
  void init(int s1,int s2) {n=s1; m=s2; memset(c,0,sizeof(c));}
  void change(int xx,int yy,int k) {
    for (int x=xx; x
<p><span>这个实现中，我们可以看出来这两重循环直接控制好了下标，那么多维直接加几重循环就完事了，xx,yy当参数名可以在后面循环写x,y，我懒……</span></p>
<p><br>
<span>没了……其实全文可能没啥新鲜的<br>
下期预告：邪道（写萎）的BIT<br>
</span></p>

Salin selepas log masuk