zkw线段树 学习笔记

前置知识

  1. C++位运算
  2. 学过线段树(其实关系不大)

什么是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<<1|1];
}
细心的读者们肯定会发现上面的计算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<<=1$(即:$now*=2$),$l$指针每向上一次GetFa都需要$l>>=1$(即:$l/=2$),$r$指针每向上一次GetFa都需要$r>>=1$(即:$r/=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<<1|1];
}
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;
}

评论

  1. yzx1798106406 博主
    2年前
    2019-2-27 19:08:32

    test

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇