zkw线段树 学习笔记

(Updated: )
oi
,

前置知识

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

什么是zkw线段树

就是一种线段树。（废话） 与普通线段树相比，zkw线段树更快、更短小。 本篇博客讲一个例题：Luogu P3372

普通线段树

zkw线段树

zkw线段树的实现

首先来看一看变量的定义与BuildTree操作

这是一棵求和的线段树（废话） 然后我们发现它有16个叶子节点。 而$16=2^{log_2(16+1)}$ 那我们定义一个N代表叶子节点的数目,n代表原数组的长度。

1
2
3
4
5
6
7
8
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

1
2
3
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结束）
}

单点查询

单点查询更简单啦

1
2
3
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$)。 注意：这次修改需要到达根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
    }
}

区间查询

与上文的区间修改差不多。只是将修改改成了查询，这里不讲了，直接放代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 直接上代码，因为就是区间修改+区间查询：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#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;
}