线段树

线段树

思想

线段树是一棵二叉树,用来维护区间信息。

树的叶子用来记录结点信息,其父亲记录所有儿子(子区间)的信息。 根节点记录的就是整个区间的信息。

通过pushup的操作,将底层信息向根结点进行反馈。

通过pushdown的操作,将标记下放。

区间合并:

对于区间合并。 我们需要维护三个值:

  1. 最长连续子区间 - mx
  2. 包含左端点的最长连续子区间 - lmx
  3. 包含右端点的最长连续子区间 - rmx

那么对mx的更新,它的可能值有三个:

  1. 左儿子的mx
  2. 右儿子的mx
  3. 左儿子的mmx + 右儿子的lmx

对于lmx的更新:

  1. 左儿子的lmx
  2. 如果左儿子的lmx值为 左儿子区间长度(lson_len) 的话,那么还要加上右儿子的lmx

对于rmx的更新:

  1. 右儿子的rmx
  2. 如果右儿子的rmx值为 右儿子的区间长度(rson_len) 的话,那么还要加上左儿子的rmx

证明:

模板

1
2
3
4
5
6
7
// 左闭右闭
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
const int maxn = "Edit";
int seg[maxn << 2];

单点更新,区间查询

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
// 左闭右闭 [l,r]
void pushup(int rt) { seg[rt] = seg[lson] + seg[rson]; }

void build(int l, int r, int rt) {
if (l == r) {
seg[rt] = num[l];
// cin >> seg[rt]; //建立的时候直接输入叶节点
return;
}
int m = (l + r) >> 1;
build(l,m,lson);
build(m+1,r,rson);
pushup(rt);
}

void update(int p, int add, int l, int r, int rt) {
if (l == r) {
seg[rt] += add;
return;
}
int m = (l + r) >> 1;
if (p <= m) update(p, add,l,m,lson);
else update(p, add, m+1,r,rson);
pushup(rt);
}
int query(int L, int R, int l, int r, int rt) { // L R 是要查询的区间
if (L <= l && r <= R) return seg[rt];
int m = (l + r) >> 1, ret = 0;
if (L <= m) s += query(L, R, l,m,lson);
if (m < R) s += query(L, R, m+1,r,rson);
return ret;
}

// update interval
// lazy[rt]用于存放懒惰标记,注意PushDown时标记的传递
const int maxn = "Edit";
int lazy[maxn << 2], seg[maxn << 2];

void pushup(int rt) { seg[rt] = seg[lson] + seg[rson]; }
void pushdown(int rt, int len) {
if (lazy[rt] == 0) return;
lazy[lson] += lazy[rt];
lazy[rson] += lazy[rt];
seg[lson] += lazy[rt] * lson_len;
seg[rson] += lazy[rt] * rson_len;
lazy[rt] = 0;
}
void build(int l, int r, int rt) {
lazy[rt] = 0;
if (l == r) {
seg[rt] = num[l];
//cin >> seg[rt];
return;
}
int m = (l + r) >> 1;
build(l,m,lson);
build(m+1,r,rson);
pushup(rt);
}
void update(int L, int R, int add, int l, int r, int rt) { // L R 是要更新的区间
if (L <= l && r <= R) {
lazy[rt] += add;
seg[rt] += add * (r - l + 1);
return;
}
pushdown(rt, r - l + 1);
int m = (l + r) >> 1;
if (L <= m) update(L, R, add, l,m,lson);
if (m < R) update(L, R, add, m+1,r,rson);
pushup(rt);
}
int query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) return seg[rt];
pushdown(rt, r - l + 1);
int m = (l + r) >> 1, ret = 0;
if (L <= m) ret += query(L, R, l,m,lson);
if (m < R) ret += query(L, R, m+1,r,rson);
return ret;
}

// interval merge
struct Seg{
int mx,lmx,rmx;
};

void pushup(int rt,int len){
seg[rt].mx = max(seg[lson].mx, max(seg[rson].mx, seg[lson].rmx + seg[rson].lmx));
seg[rt].lmx = seg[lson].lmx;
seg[rt].rmx = seg[rson].rmx;
if(seg[rt].lmx == lson_len) seg[rt].lmx += seg[rson].lmx;
if(seg[rt].rmx == rson_len) seg[rt].rmx += seg[lson].rmx;
}

Thank you for your support!