关于非递归的线段树

发表于 2016-11-07   |   分类于 线段树 , zkw  |  访问: 106 次

所谓非递归的通常是指zkw那份《统计的力量》里面的代码,说实话那份ppt不是很好理解,我也是看了好几天才懂的,不过看懂前50张也就差不多懂得精髓了。后面那个区间修改我一直感觉写得很奇怪,结果一百度很多人都说那是错误代码,反正我也看不懂后面那些什么“永久标记化”,还不如看一下有没有人看懂并且写了代码理解一下就行了。

由于画图太麻烦,我就讲一下单点修改和区间或单点查询。

朴素的线段树在修改时必修先二分递归查找到那个点然后修改它,假设咱们现在能省去递归查找的部分,一步就可以直接修改,然后进行回溯,那岂不是很省事,我们把可以一步到这个点的那个加数设为M,则修改的代码为:

void push(int x,int y){
    x+=M;
    //一步到达叶子节点
    tree[x]=y;
    x>>=1;
    while(x){
        tree[x]=max(tree[x<<1],tree[(x<<1)+1]);
        //上面这句因题而异,这里我们维护最大值
        x>>=1;
        //直接回溯
    }
}

这个应该是很容易想得懂的,所以单点查询的话自行YY(单点查询的时间复杂度应该是O(1)的,但是意义不大,通常是区间修改加单点查询和单点修改加区间查询),比较有差异的应该是区间查询。假如现在要查询[y1,y2]这个区间的最大值,朴素做法仍然是先递归查找最大的那几个区间,然后比较其最大值,这里不再赘述。那么zkw线段树是如何进行的呢。它是没有办法查询[y1,y2]的,但是它可以查的是(y1-1,y2+1),所以我们要做的事情就是先把y1加上M,再把y2加上M,然后把y1--,y2++,这样子就可以开始查询(y1-1,y2+1)这个区间,也就是做到了查询[y1,y2]这个区间的最大值。

y1和y2都已经到达叶子节点,步骤我就直接说了,至于正确性可以自己画图模拟检验。当y1为偶数的时候,我们把最大值和tree[y1+1]的位置的最大值比较一下,当y2为奇数时,我们把最大值和tree[y2-1]的位置的最大值比较一下。说多好像看不大懂,我还是画张图吧。

11111

这里能用的数组只有[1,6],0和7是不能用的因为我们每次要把y1+M-1,y2+M+1,M=8,加入现在要查询[1,6]的最大值,即y1=1,y2=6,y1加上M-1以后变成8,y2加上M+1以后变成15,8和15是线段树中的下标8和15。11111

y1=8为偶数,所以ans=max(ans,tree[y1+1])=3
y2=15为奇数,所以ans=max(ans,tree[y2-1])=3
第一次比较了tree中下标的9和14
然后y1>>=1,y2>>=1,则y1=4,y2=7,
由于y1又为偶数,所以ans=max(ans,tree[y1+1])=8
而y2为奇数,所以ans=max(ans,tree[y2-1])=8
第二次比较了tree中下标的4和7
然后y1>>=1,y2>>=1;
则y1=2,y2=3;
这个时候发现y1^y2^1==0所以结束比较
ans=8即为[1,6]中的最大值

仔细看一下把蓝色的点依次串起来可以包括里面所有最大的那几个比较区间
所以可以得到最大值

至于为什么左边为偶数的时候进行比较和右边为奇数的时候进行比较原因不得而知
反正模拟以后我们发现这个做法是没有错误的

代码的话

int query(int y1,int y2){
    y1+=M;y1--;
    y2+=M;y2++;
    int ans=-inf;  //初始化为最小值即可
    while(y1^y2^1){
        if(~y1&1)  //判断左边是否为偶数
            ans=max(ans,tree[y1^1]);
        if(y2&1)   //判断右边是否为奇数
            ans=max(ans,tree[y2^1]);
        y1>>=1;y2>>=1;
    }
    return ans;
}

这个就是简单的一个区间查询了

zkw的好处就是常数小,思想易懂好调试,代码好写,可以适用于各种线段树进行使用,最近就写了几题树链剖分+线段树的,要不是这个非递归版的线段树,估计调试都够呛

下面还有点小部分讲一下(这里假设要维护的数组称为a数组,而线段树为tree数组)

M值要怎么计算,一般来讲M=1<<(int)log2(n+1)+1,M是叶子节点前面的节点总数+1,加1是因为tree[M]这个节点我们也是用不了的,因为它对应的是a数组里面下标为0的值(而我们是从1开始储存的),所以tree空间的话似乎开a数组空间两倍就够,但保险起见我个人通常是开4倍。

能看到我们每次都要为要a数组1前面留出一个0和n后面留出一个n+1,建树的时候我们也要为这两个腾出空间,也就是说如果a数组只有2个数字,那么我们需要一棵具有三层的tree,这样叶子节点的总数才足以2+2个,而如果a数组有3个数字,那么我们需要的就是一棵四层的tree,这样叶子节点的总数才有至少3+2个。tree[M]对应的就是维护的数组里面下标为0的地方。

哪里讲得不清晰欢迎提建议或意见,QQ:838729054


补坑讲区间修改

关于区间修改,建议别用zkw写吧,,,反正我是没理解,倒不如朴素做法来得实在简单好理解
一般做法就是:
添加一个add树表示树上节点的累加值,
修改的时候不但修改当前tree[i]的add[i]值
还要把tree[i]累加上add[i]*(r-l+1)
这样每次查询的时候就是把到达tree上的i点的add值全加起来为sum
那么tree[i]的真实值就是tree[i]+sum*(r-l+1)

//在区间[y1,y2]加上v,当前tree[p]表示区间为[l,r]
void modify(int l,int r,int y1,int y2,int p){
	if(y1<=l && y2>=r){
		add[p]+=v;
		tree[p]+=v*(r-l+1);
	}
	else{
		int mid=(l+r)>>1;
		if(y1<=mid) modify(l,mid,y1,y2,p<<1);
		if(y2>mid)	modify(mid+1,r,y1,y2,(p<<1)+1);
		tree[p]=tree[p<<1]+tree[(p<<1)+1]+add[p]*(r-l+1);
	}
}
int query(int l,int r,int y1,int y2,int p,int sum){
	if(l>=y1 && r<=y2)
		return tree[p]+sum*(r-l+1);
	else{
		int temp=0;
		int mid=(l+r)>>1;
		if(y1<=mid)	temp+=query(l,mid,y1,y2,p<<1,sum+add[p]);
		if(y2>mid)	temp+=query(mid+1,r,y1,y2,(p<<1)+1,sum+add[p]);
		return temp;
	}
}

 

仅有 1 条评论


  1. lhz

    你还真他娘是个天才

    lhz September 21st, 2017 at 02:52 pm回复

发表新评论

© 2017 Powered by Typecho & Theme Quark