zkw线段树 学习笔记
zkw线段树 学习笔记
前置知识
- C++位运算
- 学过线段树（其实关系不大）
什么是zkw线段树
就是一种线段树。（废话） 与普通线段树相比，zkw线段树更快、更短小。 本篇博客讲一个例题：Luogu P3372
普通线段树
zkw线段树
zkw线段树的实现
首先来看一看变量的定义与BuildTree操作
这是一棵求和的线段树（废话） 然后我们发现它有16个叶子节点。 而16=2^{log_2(16+1)} 那我们定义一个N代表叶子节点的数目,n代表原数组的长度。
int n,m,tree[MAXN],add[MAXN],N;
inline void build(){
n=read();m=read();
for(N=1;N<=n+1;N<<=1) ;//计算N，叶子节点数目
for(int i=N+1;i<=N+n;i++) tree[i]=read();
build();
for(int i=N-1;i>=1;i--) tree[i]=tree[i<<1]+tree[i<<11];
}细心的读者们肯定会发现上面的计算N的方法计算出来为32，是16的两倍。对，这样对以后有用。
单点修改
直接放代码了QWQ
inline void add(int x,int k){//在原数组编号为x的节点加k
for(x+=N;x;x>>=1) tree[x]+=k; //x+N代表在树中这个点的编号，然后不断向上GetFa（x>>=1等价于x/=2），直到根节点操作结束（根节点编号为1，到0结束）
}单点查询
单点查询更简单啦
inline int query(int x){
return tree[x+N];//别忘记在原数组中的编号与树中的编号不同！
}区间修改
蒟蒻：区间修改复杂度不会很高吗？zkw线段树怎样让他复杂度降低呢？ 神犇：直接像线段树那样加一个可持久化标记不就好了吗？ 这是一棵树：
比如说要修改区间[7,14]。 就是修改这一段区间：
标记l为待修改区间的左标记的左边一格，标记r为待修改区间的右标记的右边一格。
那么[7,7]节点需要+k\times 1，同理，[6,7]也要+k\times 1，以此类推，但是[8,9]节点需要+k \times 2因为它的两个儿子都修改，而上文提到这是一棵求和线段树，所以需要\times 2。那么可知，[8,11]需要+k \times 4，[8,15]需要+k\times 8。 问题来了，怎么求k的系数呢？ 我们可以设now=1,CountLeft=0,CountRight=0分别表示本层包含多少个节点、l指针从叶子节点走来总共走了多少节点、r指针从叶子节点走来总共走了多少节点。那么每向上一次GetFa都需要将now<<=1now*=2)，l指针每向上一次GetFa都需要l>>=1l/=2)，r指针每向上一次GetFa都需要r>>=1r/=2)。 注意：这次修改需要到达根节点。
inline void update(int l,int r,int k){
int CountLeft=0,CountRight=0,now=1;
for(l=N+l-1,r=N+r+1;l^r^1;l>>=1,r>>=1,now<<=1){
tree[l]+=k*CountLeft;
tree[r]+=k*CountRight;
if(l%2==0) add[l^1]+=k,tree[l^1]+=k*now,CountLeft+=now;
if(r%2==1) add[r^1]+=k,tree[r^1]+=k*now,CountRight+=now;
}
for(;l;l>>=1,r>>=1){
tree[l]+=k*CountLeft;
tree[r]+=k*CountRight;
}
}区间查询
与上文的区间修改差不多。只是将修改改成了查询，这里不讲了，直接放代码：
inline int query(int l,int r){
int CountLeft=0,CountRight=0,now=1,res=0;
for(l=N+l-1,r=N+r+1;l^r^1;l>>=1,r>>=1,now<<=1){
if(add[l]) res+=add[l]*CountLeft;
if(add[r]) res+=add[r]*CountRight;
if(l%2==0) res+=tree[l^1],CountLeft+=now;
if(r%2==1) res+=tree[r^1],CountRight+=now;
}
for(;l;l>>=1,r>>=1){
res+=add[l]*CountLeft;
res+=add[r]*CountRight;
}
return res;
}关于例题
对对对，就是Luogu P3372 直接上代码，因为就是区间修改+区间查询：
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#define int long long
#define MAXN 100010*4
using namespace std;
inline int read(){
int res=0,f=1;char ch=getchar();
while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
return res*f;
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x<10) putchar(x+'0');
else{
write(x/10);
putchar(x%10+'0');
}
}
int n,m,a[MAXN],tree[MAXN],add[MAXN],N;
inline void build(){
for(int i=N-1;i>=1;i--) tree[i]=tree[i<<1]+tree[i<<11];
}
inline void update(int l,int r,int k){
int CountLeft=0,CountRight=0,now=1;
for(l=N+l-1,r=N+r+1;l^r^1;l>>=1,r>>=1,now<<=1){
tree[l]+=k*CountLeft;
tree[r]+=k*CountRight;
if(l%2==0) add[l^1]+=k,tree[l^1]+=k*now,CountLeft+=now;
if(r%2==1) add[r^1]+=k,tree[r^1]+=k*now,CountRight+=now;
}
for(;l;l>>=1,r>>=1){
tree[l]+=k*CountLeft;
tree[r]+=k*CountRight;
}
}
inline int query(int l,int r){
int CountLeft=0,CountRight=0,now=1,res=0;
for(l=N+l-1,r=N+r+1;l^r^1;l>>=1,r>>=1,now<<=1){
if(add[l]) res+=add[l]*CountLeft;
if(add[r]) res+=add[r]*CountRight;
if(l%2==0) res+=tree[l^1],CountLeft+=now;
if(r%2==1) res+=tree[r^1],CountRight+=now;
}
for(;l;l>>=1,r>>=1){
res+=add[l]*CountLeft;
res+=add[r]*CountRight;
}
return res;
}
signed main(){
n=read();m=read();
for(N=1;N<=n+1;N<<=1) ;
for(int i=N+1;i<=N+n;i++) tree[i]=read();
build();
for(int op,x,y,k,i=1;i<=m;i++){
op=read();
if(op==1){
x=read();y=read();k=read();
update(x,y,k);
}else if(op==2){
x=read();y=read();
write(query(x,y));putchar('\n');
}
}
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019-02-24
，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
