题解 P3372 【【模板】线段树1 】

看了一下题解里的zkw线段树，感觉讲的不是很清楚啊（可能有清楚的但是我没翻到，望大佬勿怪）。

决定自己写一篇。。。希望大家能看明白。。。

zkw线段树是一种优秀的非递归线段树，速度比普通线段树快两道三倍，同时代码量不大。

（当然，存在很多线段树可做zkw不可做的题）

zkw线段树的核心思路就是先修改叶子，然后从底向上沿着路径修改。

如果画一张图出来整个过程有点像逐渐两条交回在根节点的链。

注意：对于需要维护的区间$[1,n]$，zkw线段树维护的实际上是$[0,n+1]$。

建树

 inline void build(ll n){

     bit=;

     while(bit<n+)bit<<=;

     for(ll i=;i<=n;++i)tree[bit+i]=a[i];

     for(ll i=bit-;i>=;--i)tree[i]=tree[i<<]+tree[i<<|],tag[i]=;

 }

bit表示的底层的大小，我们需要先预处理出这个全局变量。

然后我们就可以先把叶子的值全部读入。

读入之后就顺着叶子向上走，更新上面的节点。

这一段代码没有什么复杂的地方。

更新

 inline void update(ll l,ll r,ll val){

     ll s,t,ln=,rn=,x=;

     for(s=bit+l-,t=bit+r+;s^t^;s>>=,t>>=,x<<=){

         tree[s]+=val*ln,tree[t]+=val*rn;

         if(~s&)tag[s^]+=val,tree[s^]+=val*x,ln+=x;

         if(t&)tag[t^]+=val,tree[t^]+=val*x,rn+=x;

     }

     for(;s;s>>=,t>>=)tree[s]+=val*ln,tree[t]+=val*rn;

 }

更新操作稍微比建树复杂一点。

s和t就是先前提到的两条链，当然准确地说，它们的轨迹才是那两条链。

ln,rn表示的是当前节点的长度（也就是s,t的长度）。

x表示的是s和t中间这一坨的长度。

然后也是一样的自底向上，每一次先更新两边，然后再判断该更新左儿子还是右儿子。

查询

 inline ll query(ll l,ll r){

     ll s,t,ln=,rn=,x=,ans=;

     for(s=bit+l-,t=bit+r+;s^t^;s>>=,t>>=,x<<=){

         if(tag[s])ans+=tag[s]*ln;

         if(tag[t])ans+=tag[t]*rn;

         if(~s&)ans+=tree[s^],ln+=x;

         if(t&)ans+=tree[t^],rn+=x;

     }

     for(;s;s>>=,t>>=)ans+=tag[s]*ln,ans+=tag[t]*rn;

     return ans;

 }

查询操作和更新一样，没什么好讲的。

不开O2跑了511ms，比普通线段树的760+ms快很多（可能是我写丑了）

完整代码如下：

 #include<bits/stdc++.h>

 using namespace std;

 typedef unsigned long long ll;

 const ll N=;

 ll n,m;

 ll op,x,y,z;

 ll a[N];

 ll bit;

 ll tree[N<<],tag[N<<];

 inline void build(ll n){

     bit=;

     while(bit<n+)bit<<=;

     for(ll i=;i<=n;++i)tree[bit+i]=a[i];

     for(ll i=bit-;i>=;--i)tree[i]=tree[i<<]+tree[i<<|],tag[i]=;

 }

 inline void update(ll l,ll r,ll val){

     ll s,t,ln=,rn=,x=;

     for(s=bit+l-,t=bit+r+;s^t^;s>>=,t>>=,x<<=){

         tree[s]+=val*ln,tree[t]+=val*rn;

         if(~s&)tag[s^]+=val,tree[s^]+=val*x,ln+=x;

         if(t&)tag[t^]+=val,tree[t^]+=val*x,rn+=x;

     }

     for(;s;s>>=,t>>=)tree[s]+=val*ln,tree[t]+=val*rn;

 }

 inline ll query(ll l,ll r){

     ll s,t,ln=,rn=,x=,ans=;

     for(s=bit+l-,t=bit+r+;s^t^;s>>=,t>>=,x<<=){

         if(tag[s])ans+=tag[s]*ln;

         if(tag[t])ans+=tag[t]*rn;

         if(~s&)ans+=tree[s^],ln+=x;

         if(t&)ans+=tree[t^],rn+=x;

     }

     for(;s;s>>=,t>>=)ans+=tag[s]*ln,ans+=tag[t]*rn;

     return ans;

 }

 int main(){

     scanf("%lld%lld",&n,&m);

     for(ll i=;i<=n;++i)scanf("%lld",&a[i]);

     build(n);

     while(m--){

         scanf("%lld%lld%lld",&op,&x,&y);

         if(op==)scanf("%lld",&z),update(x,y,z);

         else cout<<query(x,y)<<endl;

     }

 }

巴特西

题解 P3372 【【模板】线段树1 】

最新文章

热门文章