树状数组延伸和离线优化(CDQ、整体二分和莫队)-myt

树状数组延伸和离线优化（CDQ、整体二分和莫队）数据结构离线优化树状数组1、一般树状数组1.intlowbit(intx){2.returnx&(-x);3.}4.longlongsum(longlonga[],intend){5.longlongres=0;6.while(end){7.res=res+a[end];8.end=end-lowbit(end);9.}10.returnres;11.}12.voidmodify(longlonga[],intp,intd){13.while(p=n){14.a[p]+=d;15.p=p+lowbit(p);16.}17.}一般树状数组的特点：单点更新，区间查询。2、区间更新例子：POJ3468题意：给出N个数，M个操作，操作分为2种：查询[l,r]的和；给[l,r]中每个数加上d。N,M=10^5;线段树当然可以做。但是线段树占用的空间和时间都是树状数组的常数倍，所以还是优先使用树状数组。如何修改原有的树状数组是的它能使用区间更新呢。STEP1：更新操作：把[l,r]所有的数加上d，可以看做把[l,n]所有数加上d，再把[r+1,n]所有数减去d。那我们引入一个新的数组delta[n]，delta[i]记录了[i,n]每个数的增量。操作就转化为了delta[l]+=d,delta[r+1]-=d;SETP2:查询操作：求[l,r]的和，当然是看做求sum[1,r]-sum[1,l-1]啦。就是求sum(x)。首先，要加上原数组的基数前缀和origin[x]，这个一开始就能求出来。然后，考虑delta数组，delta[1]为[1,x]贡献了x个delta[1]，delta[2]为[2,x]贡献了x-1个delta[2]，以此类推，delta[i]贡献了(x+1-i)个delta[i]。那么这样子，屌屌的，求整体前缀和就分解成了求3个前缀和。此时，origin可以预处理出来。delta[i]和delta[i]*i的每次更新都是单点的更新的。便彻底转化成了一般树状数组了。3、二维树状数组代码很好写，就是把原来的一维改成二维，一看就懂的。1.intlowbit(intx){2.returnx&(-x);3.}4.intsum(intx,inty){5.intres=0;6.for(inti=x;i0;i-=lowbit(i))7.for(intj=y;j0;j-=lowbit(j))8.res=res+c[i][j];9.returnres;10.}11.intmodify(intx,inty,intd){12.for(inti=x;i=n;i+=lowbit(i))13.for(intj=y;j=n;j+=lowbit(j))14.c[i][j]+=d;15.}例子：POJ2155题意：一块N*N的矩阵，一开始每个点都是0，有M个操作，操作分为2种：将矩阵（x1,y1)-(x2,y2)中的所有点取反；询问点(x,y)的值。STEP1:点(x,y)的值等于点(x,y)取反次数cnt[x][y]%2STEP2:将(x1,y1)-(x2,y2)取反操作，分解为：将(x1,y1)-(n,n)取反=m[x1][y1]++;将(x1,y2+1)-(n,n)取反=m[x1][y2+1]++;将(x2+1,y1)-(n,n)取反=m[x2+1][y1]++;将(x2+1,y2+1)-(n,n)取反=m[x2+1][y2+1]++;STEP3:求cnt[x][y]就是求可解。4、二维树状数组区间更新其实就和一维区间差不多，公式化简下来会出现5个前缀和，分别为：原数组基数前缀和常系数delta[x][y]前缀和仅x系数delta[x][y]前缀和仅y系数delta[x][y]前缀和xy系数delta[x][y]前缀和分别维护即可。CDQ分治、整体二分和莫队Preface：由于网上写关于CDQ和整体二分的一大部分谐星也自己没有搞清楚这两者有个毛线区别，挖了一个又一个史前巨坑给我，我真是&*（￥#%@&￥%#！但是这两者有个共同点，就是用于对离线和允许在线转离线的问题。CDQ分治模型很简单：1：将操作按照某个关键字排序2；算出[L,mid]对[mid+1,R]的贡献3；solve[L,mid]和solve[mid+1,R]注意：这里的区间指的是操作ID区间这东西讲起道理来无聊的一比，直接上题。Description维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M=160000,询问数Q=10000,W=2000000.Input第一行两个整数,S,W;其中S为矩阵初始值;W为矩阵大小接下来每行为一下三种输入之一(不包含引号):“1xya”“2x1y1x2y2”“3”3表示Case结束显然你是不能依靠二维树状数组做的，因为W这货大的一比，离散化以后依然大的一比。电子竞技没有如果和万一。。。那么怎么搞。为了方便表示，x代表行，y代表列STEP1：将求(x1,y1)-(x2,y2)分解为求(1,1)-(x2,y2)&&(1,1)-(x2,y1-1)&&(1,1)-(x1-1,y2)&&(1,1)-(x1-1,y1-1)四个矩形的关系。即转化为了求4个二维前缀和。以下（1,1)-(x,y)的和简写为sum(x,y);STEP2：将所有共K个操作——修改加询问，按输入顺序给予ID（此时原询问被分解为4个子询问），然后按照他们的x属性排序。STEP3：建立一颗大小为W的树状数组，c[i]记录前i列的和。在这里，如果对矩阵的修改是按照x从小到大的顺序的话，那么求sum(x,y)其实就是求前y列的和，这里很关键。STEP4：Solve(1,K），设mid=(1+K)/2，建立两个队列Q1,Q2.然后遍历1到K个操作：①如果此操作为修改，同时操作ID≤mid，add(opt.y,opt.d);②如果此操作为询问，同时操作IDmid，ans+=query(opt.y);③如果此操作ID≤mid，插入Q1④如果此操作ID＞mid，插入Q2这个地方啊，真的是很屌啊。首先，只进行ID≤mid的修改，只进行ID大于mid的查询，这样，按x排序和输入顺序就不冲突了。成功的算出了[L,mid]对[mid+1,R]的贡献，同时更新[mid+1,R]中查询的值。STEP5：遍历1到K个操作：如果此操作为修改，同时操作ID≤mid,add(opt.id,-opt.d)即还原修改，因为贡献已经用于更新了，所以清零就好了。STEP6:solve(Q1);solve(Q2);[L,mid]对[mid+1,R]的贡献已经更新了，那么[L,mid]和[mid+1,R]就毛关系没有了，那么只要考虑[L,mid]和[mid+1,R]自身就好了。于是、、、靠、、、这TM就是CDQ分治、、、复杂度分析：分治复杂度log(n)每次树状数组操作log(s)其实复杂度和那个啥树套树啥的差不多，虽然我不会、、、但是，你想啊：1.voidsolve(intl,intr){2.intmid=...3.for(inti=l;i=r;i++){4.if(condition1)...①如果此操作为修改，同时操作ID≤mid，add(opt.id,opt.d);5.if(condition2)...①如果此操作为修改，同时操作ID≤mid，add(opt.id,opt.d);6.if(condition3)...7.else...③如果此操作ID≤mid，插入Q18.④如果此操作ID＞mid，插入Q29.}10.for(inti=l;i=r;i++)11.if(condition1)...还原修改12.solve(q1);solve(q2);13.}从此树套树粉转路人。虽然看上去貌似不难，但是如何在O(n)的复杂度内算出[l,mid]对[mid+1,R]的贡献，是解题的关键整体二分其实整体二分是二分答案的一个进化版。真的代码看上去和CDQ几乎一模一样。但是整体二分是对答案进行二分，然后再对操作进行二分归类。注意：整体二分的操作顺序是不能改变的模型也简单的一比1；确定答案范围[L,R],mid=(L+R)/2;2；算出答案在[L,mid]内的操作对答案在[mid+1,R]内的操作的贡献3；将答案在[L,mid]内的操作放入队列Q1，solve(Q1,L,mid)将答案在[mid+1,R]内的操作放入队列Q2，solve(Q2,mid+1,R)注：这里的区间指的是答案区间例题：动态区间第k小1~N个数，M个操作，操作分为2种：将x位置的数改为y；求[x,y]内的第k小数STEP1：将修改操作分解为2个子操作：去掉原先的数a，插入一个新数b。这在后面会有用。设这样之后所有操作数为KSTEP2：新建一个树状数组C和2个队列Q1，Q2，c[i]存储的是小于等于mid的数的个数。STEP3；确定答案范围[L,R]，同时二分答案mid=(L+R)/2;然后遍历1到K个操作：①如果是修改操作，且插入/删去的数≤mid，add(opt.x,±1）&&塞入Q1否则如果大于mid，不更新&&塞入Q2②如果是询问操作，且sum(opt.y)-sum(opt.x-1)=opt.k，塞入Q1，否则，opt.k=opt.k-[sum(opt.y)-sum(opt.x-1)]&&塞入Q2这个要比CDQ好理解一点。就是对于一个猜想答案mid。小于等于mid的修改放到Q1，大于mid的放到Q2；答案小于等于mid的查询放到Q1，答案大于mid的查询，减去小于mid的总贡献，然后放到Q2。即更新[L,mid]操作对[mid+1,R]询问的贡献，并分类STEP4：还原更新STEP5：solve(Q1,L,mid);solve(Q2,mid+1,R)其实到这里，仔细想想，两种方法根本没差，就是如何将所有操作分成可以互不相关的两半，同时快速更新贡献的问题。莫队算法莫队的适用范围就稍微小一点了。它貌似只能用于离线的区间查询，并且区间[L,R]的答案转移到[L,R+1]的答案必须在O（1）的时间内完成。但是实用性还是可以的。例题：CF617E给出N个数和常数K，然后给出M个询问，每个询问L,R求[L,R]中有多少个数对（i,j)i=j，使得显然，最朴素的方法O(N^3)：（算法1）1.for(inti=0;iM;i++){2.cinlrk;3.for(intj=l;j=r;j++){4.intres=0;5.for(intt=j;t=r;t++)res=res^A[t];6.if(res==k)cnt++;7.}8.}但是，来，让我们自己看看Ai到Aj的xor积=（A1到Ai-1的xor积）xor（A1到Aj的xor积）；即设f(i)=A1xorA2xor....Ai题目转化为，求[l,r]中有多少数对是的f[i]xorf[j]=k；那我们可以预处理出f数组。同时我们建立数组cnt，cnt[i]表示f[j]=i(l=i=r)的j的个数。Ans表示当前然后考察查询[l,r]和[l,r+1]之间的关系。在加入了A[r+1]后:Ans=Ans+cnt[k^f[r+1]];cnt[f[r+1]]++只需要O（1）的复杂度，靠，屌！那么复杂度就可以降低算法2：1.for(inti=0;im;i++){2.doL-q[i].l;3.doR-q[i].r;4.}最坏复杂度的为O（n^2）就是[1,1]-[N,N]-[1,1].....接下来这么操作STEP1：将所有查询按L从小到大排序STEP2：将查询从小到大，l/sqrt(n)相同的查询个分成一组，每组内按照R从小到大排序STEP3：GOTO算法3此时，我们原封不动的使用算法3，但是，牛逼的是，让我们算一算复杂度。排序O(mlogm)算法3复杂度：左边界和右边界的移动量分别考虑左边界：每次最多移动sqrt(n)，左边界移动复杂度O(msqrt(n))右边界：共