区间rmq的zkw线段树

Posted by Cww97 on 2017-08-04

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/76652752
本文适合对线段树有一定理解,同时看过一点《统计的力量》的人

zkw线段树的理解和思考

zkw线段树解决区间rmq

zkw线段树具体内容请百度统计的力量(这是他讲的时候所用的ppt的名字)

今天我们就来完整的写一个zkw线段树。

正如他在ppt里讲的
差分是化绝对为相对的重要手段
标记永久化后就是值,只不过这种值是相对的
*计算答案时可以利用从节点到根部的信息

在zkw树中,每个节点存的都不是最大值M[x], 而是M[x] - Mx<<1。这样有什么用呢?你可以试一下从某个结点开始,走到根,你会发现一路上的和加起来,就是这里存在最大值。这样,单点Query就解决了。单点更新也比较简单,就是一点一点从叶子结点处开始修改,维护这棵树作为差分树的性质。只这样看的话,并不比普通的线段树有多大优势。

所以接下来我们看区间更新和区间查询。

区间更新时,由于是整个区间都变化,这就造成什么了呢,如果有两个叶子节点都在要更新的区间里,他俩父亲相同,而且他俩也非端点,这时,由于他俩是一起更新的,你会发现这时他俩的相对差值仍为变化,而且,由于他们自身存的是差分值,而且他们的最大值也同等增加了相同值,所以这俩个节点存的值并不需要改变,需要改变的是哪里呢?就是边界节点和跟边界节点通父亲的点,这样底层的更新最多4个点。解决完底层,它的上一层也是同理,从而每层都最多只要四个点。当左右边界同父亲的时候,在往上都只要更新两个点。这时在和线段树比较的话,你会发现,更新的点的个数少了很多有木有,当更新的层数越来越深的时候,zkw树至多4k个点,而普通线段树则是2^k个点左右。这时赤裸裸的差距啊有木有。

至于区间查询,由于每个点存的内容都和它的儿子没有关系,所以某种意义上我们可以直接找到区间的边界点,然后开始一层一层向上累加去个最大or最小就可以了。但是这个找边界点的过程还会浪费点地方。不如直接就从边界的叶子节点处一层一层向上累加,每到一层,都注意去最大or最小,来维护答案。

然后就是他的ppt中的错误,第一处在add函数里,它没有上浮到根节点,这样的话单就下次查询来说,并不会造成什么(你可以试试,这是从某点一直到根的路径中的sum仍为这个点存的Max),但是,如果有了另一次更新,这时,就会出现问题(出个数据模拟一下就可以)。所以在add函数的尾部还要加一部上浮到根节点的语句。

第二处在Query函数中,如果这时查询的不是区间是点,这时会有l=r,进一次循环,你发现l=r=0,这时,很明显,函数最后的那步上浮到根节点的循环是出不去了。

第三处仍在Query函数中,那就是这时的查询不再是开区间了,而是闭区间。比如区间的左节点是某个点的右儿子,那么这时的开区间头便是某个点的左儿子。这时按照zkw的惯例,下次的开区间节点就是他的父亲了,但是由于他的父亲的儿子中有区间内的点,从而这个父亲也算区间内的点,那么这时会出现了矛盾,也就是说,本来要经历的点却没有经历。这样肯定就有问题了,所以我们只能闭区间查询,这样才不会发生上浮一层之后,点与区间的位置关系发生改变。

今天以前,单点修改的线段树都是使用zkw的,

区间修改的,用for循环build,剩下的还是更常规线段树一样

我也不知道为何自己对这种毒瘤线段树这么狂热

去年给zkw发邮件,问他ppt是不是错了,他说没错,让我弄个小数据模拟 QAQ

快,短,常数小

真正比赛谁在意呢,我就喜欢这么写你来打我啊

区间和的还是不会写,zkw说的前缀和的前缀和太玄学了

这里的大M和引用的里面的不一样

原文里是叶子节点的数量,我这里是非叶子节点的数量(相差1)

这样在n = 1的时候cf wa了一次,cf的数据真的强, cf真的良心

《挑战》上的M也是叶子节点,我就继续我的毒瘤吧,

我已经很难追究zkw的ppt上M到底是哪个,这么多年已经习惯这种写法

能A的前提下,自己舒服就好

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 6e5 + 10;
const LL INF = 0x3f3f3f3f3f3f3f3f;

struct segmentTree{
LL tree[N];
int M, n;

void build(int n){
this->n = n;
M = 1;while (M < n) M <<= 1;if (M!=1) M--;
for (int t = 1 ; t <= n; t++) scanf("%I64d", &tree[t+M]);
for (int t = n+1; t <= M+1; t++) tree[t+M] = INF;
for (int t = M; t >= 1; t--) tree[t] = min(tree[t<<1], tree[t<<1^1]);
for (int t = 2*M+1; t >= 1; t--) tree[t] = tree[t] - tree[t>>1];
}

void update(int l, int r, LL val){
LL tmp;
for (l+=M-1, r+=M+1; l^r^1; l>>=1, r>>=1){
if (~l&1) tree[l^1] += val;
if ( r&1) tree[r^1] += val;
if (l > 1) tmp = min(tree[l], tree[l^1]), tree[l]-=tmp, tree[l^1]-=tmp, tree[l>>1]+=tmp;
if (r > 1) tmp = min(tree[r], tree[r^1]), tree[r]-=tmp, tree[r^1]-=tmp, tree[r>>1]+=tmp;
}

for (; l > 1; l >>= 1){
tmp = min(tree[l], tree[l^1]), tree[l]-=tmp, tree[l^1]-=tmp, tree[l>>1]+=tmp;
}
tree[1] += tree[0], tree[0] = 0;
}

LL query(int l, int r){
LL lAns = 0, rAns = 0;
l += M, r += M;
if (l != r){
for (; l^r^1; l>>=1, r>>=1){
lAns += tree[l], rAns += tree[r];
if (~l&1) lAns = min(lAns, tree[l^1]);
if ( r&1) rAns = min(rAns, tree[r^1]);
}
}
LL ans = min(lAns + tree[l], rAns + tree[r]);
for (;l > 1;) ans += tree[l>>=1];
return ans;
}
} T;

int main(){
///freopen("in.txt", "r", stdin);
int n, m, l, r;
for (LL x; ~scanf("%d", &n);){
if (n == -1){

}else{
}
T.build(n);
scanf("%d", &m);
for (; m--;){
scanf("%d%d", &l, &r);
l++, r++;
char ch = getchar();
if (ch == ' ') {
scanf("%I64d", &x);
if (l <= r) T.update(l, r, x);
else T.update(1, r, x), T.update(l, n, x);
}else{
if (l <= r) printf("%I64d\n", T.query(l, r));
else printf("%I64d\n", min(T.query(1, r), T.query(l, n)));
}
}
}
return 0;
}