当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 解析·优化 ZKW线段树

解析·优化 ZKW线段树

2018年10月31日  | 移动技术网IT编程  | 我要评论

品牌商城,衣服百搭,女人的战争之肮脏的交易迅雷下载

德鲁伊！大自然已经听命于我了！
死亡之翼长子奈法利安

zkw天下第一！
摘自某群聊天记录

zkw线段树，即非递归形式的线段树，出自终极大犇zkw的论文《统计的力量》。与普通的线段树相比，zkw线段树由于是非递归形式，效率极高，代码也极短，成为了oi比赛中极为实用的优化算法之一。虽然zkw线段树无法处理有运算优先级的线段树问题，但是在一般的问题上和常数偏大的问题上总能带来极强的游戏体验。

zkw线段树的建树

普通线段树
       1
      / \
     2   3                     <---------------"弱小，可伶又无助"
    / \ 
   4   5
zkw线段树
         1
       /   \
     10     11                     <---------------"天下第一！"
    / \     / \
  100 101 110 111

那么接下来进入我们的分析环节：小学生找规律。
通过观察，我们可以发现：线段树对应叶子节点的下标和原数组的下标的差值是恒定的
事实上，这个值几乎恒等于线段树数组里叶子节点的数量。
事实上，该值\(num\)满足：\[num=2^{[log_2(n+1)]} \]
于是我们可以先将线段树建为一棵满二叉树，然后我们从叶子节点开始回溯即可。
定义

#define maxn 10000
int n,num;
int minv[maxn<<2];

其中，minv为线段树数组，n为总节点数量，n即为上文提到的n。
那么完整的建树代码如下

inline int ksm(int x,int y){
    int res=1;
    while(y){
        if(y&1)res*=x%p;
        x*=x%p;
        y>>=1;
    }
    return res;
}
inline void build(){
  scanf("%d", &n);
  n=ksm(2,log2(n+1));
  for(register int i=n+1;i<=n+n;i++)cin>>minv[i];
  for(register int i=n-1;i>=1;i--)minv[i]=minv[i<<1]+minv[i<<1|1];
}

zkw线段树的修改&查询

单点修改与单点查询

代码量很少，背模板即可

单点更新
inline void update(int x,int k){
    for(register int i=x+n;i;i>>=1)tree[i]+=k;
}
区间(单点)查询
inline int query(int l,int r){
    int ans=0;
    for(l=n+l-1,r=n+r+1;s ^ r ^ 1;s>>=1,r>>=1){
        if(~s&1)ans+=tree[s ^ 1];
        if(r&1)ans+=tree[r ^ 1];
    }
    return ans;
}
zkw线段树单点操作
#include<bits/stdc++.h>
#define maxn 10000
using namespace std;
int n,n;
int a[maxn];
int ansv[maxn<<2];
inline int ksm(int x,int y){
    int res=1;
    while(y){
        if(y&1)res*=x%p;
        x*=x%p;
        y>>=1;
    }
    return res;
}
inline void build(int n){
  n=ksm(2,log2(n+1));
  for(register int i=n+1;i<=n+n;i++)ansv[i]=a[i];
  for(register int i=n-1;i>=1;i--)ansv[i]=ansv[i<<1]+ansv[i<<1|1];
}
inline void update(int x,int k){
    for(register int i=x+n;i;i>>=1)ansv[i]+=k;
}
inline int query(int l,int r){
    int ans=0;
    for(l=n+l-1,r=n+r+1;s ^ r ^ 1;s>>=1,r>>=1){
        if(~s&1)ans+=tree[s ^ 1];
        if(r&1)ans+=tree[r ^ 1];
    }
    return ans;
}

区间修改与区间查询

与普通线段树类似的，我们在zkw线段树上也不能使用暴力的方式进行区间修改。在zkw线段树上做暴力修改的复杂度甚至比普通线段树更高。同时，在zkw线段树中我们仍然需要使用到lazy标记。然而不同的是，在zkw线段树中我们会将lazy标记永久固化，即永远不对标记做pushdown操作。
我们假定现在指定了一个区间\([l,r]\)，使得区间的每一个值全部加上\(k\)，并使得\(l=2,r=10\)。
当\(l\)到了\([2,2]\)节点时，显然\([3,3]\)节点需要被标记上\(k\)，那么接下来我们走到的\([2,3]、[0,3]\)节点都会被标记上\(k*1\)，等我们到达\([0,7]\)节点时，因为\([4,7]\)已经被标记了\(k\)，所以\([0,7]\)节点的值要加上\(k*(1+4)=k*5\)，自然我们需要一个变量来存储\(k\)的系数。
需要注意的是，这次的修改要上推到根节点

inline void update(int l,int r,int k) {
    int lnum=0,rnum=0,nnum=1;
    for(l=n+l-1,r=n+r+1;l ^ r ^ 1;l>>=1,r>>=1,nnum<<=1){
        ansv[l]+=k*lnum;
        ansv[r]+=k*rnum;
        if(~s&1){
            lazy[s ^ 1]+=k;
            ansv[s ^ 1]+=k*nnum;
            lnum += nnum;
        }
        if(t&1){
            lazy[t ^ 1]+=k;
            ansv[t ^ 1]+=k*nnum;
            rnum+=nnum;
        }
    }
    for(;l;l>>=1,r>>=1){
        ansv[l]+=k*lnum;
        ansv[r]+=k*rnum;
    }    
}

区间查询的过程类似。

inline int query(int l, int r){
    int lnum=0,rnum=0,nnum=1;
    int ans=0;
    for(l=n+l-1,r=n+r+1;l ^ r ^ 1;l>>=1,r>>=1,nnum<<=1){
        if(lazy[l])ans+=lazy[l]*lnum;
        if(lazy[r])ans+=lazy[r]*rnum;
        if(~l&1){
            ans+=ansv[l ^ 1];
            lnum+=nnum;
        }
        if(r&1){
            ans+=ansv[r ^ 1];
            rnum+=nnum;
        }
    }
    for(;l;l>>=1,r>>=1) {
        ans+=lazy[l]*lnum;
        ans+=lazy[r]*rnum;
    }
    return ans;
}
线段树区间操作代码
#include<bits/stdc++.h>
#define maxn 10000
using namespace std;
int n,n;
int a[maxn];
int ansv[maxn<<2],lazy[maxn<<2];
inline int ksm(int x,int y){
    int res=1;
    while(y){
        if(y&1)res*=x%p;
        x*=x%p;
        y>>=1;
    }
    return res;
}
inline void build(int n){
  n=ksm(2,log2(n+1));
  for(register int i=n+1;i<=n+n;i++)ansv[i]=a[i];
  for(register int i=n-1;i>=1;i--)ansv[i]=ansv[i<<1]+ansv[i<<1|1];
}
inline void update(int l,int r,int k) {
    int lnum=0,rnum=0,nnum=1;
    for(l=n+l-1,r=n+r+1;l ^ r ^ 1;l>>=1,r>>=1,nnum<<=1){
        ansv[l]+=k*lnum;
        ansv[r]+=k*rnum;
        if(~l&1){
            lazy[l ^ 1]+=k;
            ansv[l ^ 1]+=k*nnum;
            lnum += nnum;
        }
        if(r&1){
            lazy[r ^ 1]+=k;
            ansv[r ^ 1]+=k*nnum;
            rnum+=nnum;
        }
    }
    for(;l;l>>=1,r>>=1){
        ansv[l]+=k*lnum;
        ansv[r]+=k*rnum;
    }    
}
inline int query(int l, int r){
    int lnum=0,rnum=0,nnum=1;
    int ans=0;
    for(l=n+l-1,r=n+r+1;l ^ r ^ 1;l>>=1,r>>=1,nnum<<=1){
        if(lazy[l])ans+=lazy[l]*lnum;
        if(lazy[r])ans+=lazy[r]*rnum;
        if(~l&1){
            ans+=ansv[l ^ 1];
            lnum+=nnum;
        }
        if(r&1){
            ans+=ansv[r ^ 1];
            rnum+=nnum;
        }
    }
    for(;l;l>>=1,r>>=1) {
        ans+=lazy[l]*lnum;
        ans+=lazy[r]*rnum;
    }
    return ans;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网