线段树经典模型

segTree-01
segTree-02

Kingdom UVALive4730
UVALive4730-01
UVALive4730-02

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
class segTree {
public:
struct node {
int l, r;
int sum1, sum2;
int tag1, tag2;

void apply1(int v) {
tag1 += v;
sum1 += v * (r-l+1);
}
void apply2(int v) {
tag2 += v;
sum2 += v * (r-l+1);
}
};

inline void push(int p) {
if (t[p].l != t[p].r && t[p].tag1) {
t[p<<1].apply1(t[p].tag1);
t[p<<1 | 1].apply1(t[p].tag1);
t[p].tag1 = 0;
}
if (t[p].l != t[p].r && t[p].tag2) {
t[p<<1].apply2(t[p].tag2);
t[p<<1 | 1].apply2(t[p].tag2);
t[p].tag2 = 0;
}
}
inline void pull(int p) {
int lc = p<<1, rc = p<<1 | 1;
t[p].sum1 = t[lc].sum1 + t[rc].sum1;
t[p].sum2 = t[lc].sum2 + t[rc].sum2;
}

void change(int p, const int l, const int r, int add1, int add2) {
if (l <= t[p].l && t[p].r <= r) {
t[p].apply1(add1), t[p].apply2(add2);
return;
}

push(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid) change(p<<1, l, r, add1, add2);
if (r > mid) change(p<<1 | 1, l, r, add1, add2);

pull(p);
}

void build(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if (l >= r) return;
int mid = (l+r) >> 1;
if (l <= mid) build(p<<1, l, mid);
if (r > mid) build(p<<1 | 1, mid+1, r);
}

void query(int p, const int C) {
if (t[p].l == t[p].r) {
printf("%d %d\n", t[p].sum1, t[p].sum2);
return;
}
push(p);

int mid = (t[p].l + t[p].r) >> 1;
if (C <= mid) query(p<<1, C);
else query(p<<1 | 1, C);
}

int n;
vector<node> t;

segTree() = default;
segTree(int _n) : n(_n) {
assert(n > 0);
t.resize(n << 2);
}
void clear() {
fill(t.begin(), t.end(), node());
}
};

int R, n;
const int maxn = 100000 + 10, inf = 0x3f3f3f3f;
int cnt[maxn], pa[maxn], ymax[maxn], ymin[maxn];
typedef pair<int, int> PII;
PII a[maxn];
segTree seg(maxn);

void init() {
seg.clear();
for (int i = 0; i < maxn; i++) pa[i] = i;
memset(cnt, 0, sizeof cnt);
memset(ymax, 0, sizeof ymax);
memset(ymin, inf, sizeof ymin);
}

int get(int x) {
return pa[x] == x ? x : pa[x] = get(pa[x]);
}

void prework(int R) {
seg.build(1, 0, R);
for (int i = 0; i < n; i++) seg.change(1, a[i].second, a[i].second, 1, 1);
}

void solve(int R) {
int m;
scanf("%d", &m);
while (m--) {
char str[5];
scanf("%s", str);
if (str[0] == 'r') {
int A, B;
scanf("%d%d", &A, &B);
A = get(A), B = get(B);
if (A == B) continue;

seg.change(1, ymin[B], ymax[B], -1, -cnt[B]);
seg.change(1, ymin[A], ymax[A], -1, -cnt[A]);

pa[B] = A, cnt[A] += cnt[B];
ymin[A] = min(ymin[A], ymin[B]), ymax[A] = max(ymax[A], ymax[B]);
seg.change(1, ymin[A], ymax[A], 1, cnt[A]);
}
else {
double _C;
scanf("%lf", &_C);
int C = _C * 2;

if (C > R) puts("0 0");
else seg.query(1, C);
}
}
}

int main() {
freopen("input.txt", "r", stdin);
int T;
cin >> T;
while (T--) {
init();
scanf("%d", &n);
R = 0;
for (int i = 0; i < n; i++) {
int x, y;
scanf("%d%d", &x, &y);
y <<= 1;
R = max(R, y);
a[i] = {x, y};
ymax[i] = ymin[i] = y;
cnt[i] = 1;
}

prework(R);
solve(R);
}
}

可持久化权值线段树

区间第 k 小

下面来看一种特殊的线段树,即权值线段树
权值线段树经常用于处理区间第kk 小的问题中
假设序列A={a1,a2,,an}={2,6,12,3}A = \{a_1, a_2, \cdots , a_n\} = \{-2, -6, 12, 3\}

  • 先将序列离散化成{2143}\{2, 1, 4, 3\},来看一下如何用线段树找第kk

  • for i[1,n]\textbf{for} \ \forall i \in [1, n]对每个ii 都建立一棵表示区间[1,i][1, i] 的线段树
    在每个ii 上查询区间[1,i][1, i] 的第kk 小,复杂度是O(logn)O(\log n)
    从前往后扫描序列[1,n][1, n],对于第ii 棵线段树,我们可以将第i1i-1 棵线段树复制过来,然后再修改
    wsegTree

  • 对于第ii 棵线段树和第jj 棵线段树(i<j)(i < j),二者的拓扑结构完全一样,唯一的区别就是每个点的权值不同
    由于节点权值为: 节点表示的区间[l,r][l, r] 中有多少个元素?
    由前缀和思想,对于询问区间[L,R][L, R]tree(R)tree(L1)tree(R) - tree(L-1) 就表示[L,R][L, R] 中有多少个元素
    tree(P)=tree(R)tree(L1)tree(P) = tree(R)-tree(L-1) 仍然为一棵线段树,每个节点的拓扑结构不变,权值相减

  • 这样就等于在tree(P)tree(P) 上找第kk 小,利用二分思想

    • 如果tree(P).lefttree(P).left 中元素个数K\geqslant K,递归在tree(P).lefttree(P).left 中找第KK
    • 否则,令K=Kcnt(tree(P).left)K' = K-cnt(tree(P).left),在tree(P).righttree(P).right 中找第KK'

对上述线段树进行可持久化
综上分析可以发现,算法的时间复杂度非常好,但是空间复杂度是O(n2)O(n^2)
观察这几棵线段树发现,实际上第ii 棵线段树与第i1i-1 棵线段树比
只有加粗的部分不一样,剩下的都一样,加粗部分路径即发生修改的路径,
我们只要存储修改路径上的节点就可以了,如下图所示

wsegTree-02

重要的细节
为了方便定位到每一棵线段树,需要建立一个root[]root[\cdots] 数组
记录第ii 棵线段树根节点的编号(或者说是数组地址)

K-th number
第 K 大数

细节,主席树执行单点修改的时候,是基于历史版本prepre
change(pre,l,r,x), t[pre]\textbf{change}(pre, l, r, x), \ t[pre] 表示历史版本prepre 的根节点
t[pre]t[pre] 表示的区间对应于[l,r][l, r],令mid(l+r)/2mid \leftarrow (l+r)/2

  • t[tpre.l]t[t_{pre}.l] 对应于区间[l,mid][l, mid]
  • t[tpre.r]t[t_{pre}.r] 对应于区间[mid+1,r][mid+1, r]

主席树执行单点修改

  • 新建一个第ii 阶段版本的新根节点t[i]t[i],基于旧版本prepre根节点,对第ii 阶段的新根节点进行修改
    t[pre]update: f(P)t[i]t[pre] \xrightarrow{\text{update}: \ f(P)} t[i],执行f(P)f(P) 操作
  • 自顶向下递归历史版本的线段树,递归对tpret_{pre}子树进行修改
    • 如果xmidx \leqslant mid,那么基于历史版本t[tpre.l]t[t_{pre}.l],对区间[l,mid][l, mid] 执行f(P)f(P) 操作,并且建立新节点uu
      递归返回新节点编号uu,并且令t[i].l=ut[i].l = u
    • 如果x>midx > mid,基于历史版本t[tpre.r]t[t_{pre}.r] 修改区间[mid+1,r][mid+1, r] 并且建立新节点uu
      递归返回,令t[i].r=ut[i].r = u

主席树查询区间[u,v][u, v]kk 小,利用前缀和思想,令uu1,vvu \leftarrow u-1, v \leftarrow v
考虑t[u]t[u]t[v]t[v] 这两棵线段树

  • 注意到版本uu 表示的线段树t[u]t[u] 和版本vv 表示的线段树t[v]t[v] ,对区间的划分是相同的
    都表示区间[1n][1\cdots n],因为我们是从前往后遍历,在区间中执行单点增加
    • t[u]t[u] 这棵线段树,表示区间是[1u][u+1n][1\cdots u] \cup [u+1 \cdots n]
      实际上我们只统计了[1u][1\cdots u] 的信息,对于[un][u \cdots n] 中的点,其权值为00
      所以t[u]t[u] 这棵线段树,等价于存储了[1u][1\cdots u] 区间内一共有多少个点
      其表示的区间为[l,r]=[1,n][l, r] = [1, n](对于[u+1,n][u+1, n] 中的点,其权值为00,因为在版本uu 并未添加uu 之后的点)
    • 同理,t[v]t[v] 这棵线段树存储了[1v][1\cdots v] 区间内一共有多少个点
      x=t[v]t[u]x = t[v] - t[u] 表示区间[u+1,v][u+1, v] 中一共有xx 个点
      (实际上根节点表示的区间一般仍然为[1,n][1, n],只不过vv 之后的点并没有添加,所以[v+1,n][v+1, n] 的权值为00
  • x=tv.sumtu.sumx = t_v.sum - t_u.sum 表示区间[u+1,v][u+1, v] 中有xx 个数,那么第kk 小可以用二分思想解决
    由于这两个版本的线段树对于区间的划分完全一致,所以同时递归这两棵线段树
    这两棵线段树根节点表示区间为[l,r]=[1,n], mid=(l+r)/2[l, r]=[1,n], \ mid = (l+r)/2
    根节点的地址为u=root(u1),v=root(v)query(u,v,l,r,K):u = root(u-1), v = root(v)\quad query(u, v, l, r, K):
    (是u1u-1 不是uu,因为我们询问区间[u,v][u, v])
    • t[tu.l], t[tv.l]t[t_u.l], \ t[t_v.l] 表示区间[l,mid][l, mid], 其中的元素个数为cnt=t[tv.l].sumt[tu.l].sumcnt = t[t_v.l].sum - t[t_u.l].sum
      如果KcntK \leqslant cnt,同时递归左子树,query(tu.l, tv.l, l,mid,K)query(t_u.l, \ t_v.l, \ l, mid, K)
    • t[tu.r],t[tv.r]t[t_u.r], t[t_v.r] 表示区间[mid+1,r][mid+1, r],如果K>cntK > cnt,那么同时递归右子树
      在右子树中找到第KcntK - cnt 小的元素,query(tu.r, tv.r, mid+1,r,Kcnt)query(t_u.r,\ t_v.r, \ mid+1, r, K-cnt)
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
class wsegTree {
public:
struct node {
int l, r;
int sum;
};

int n;
int tot;
vector<node> t;

wsegTree() = default;
wsegTree(int _n) : n(_n) {
assert(n > 0);
tot = 0;
t.resize(n << 5);
}
void clear() {
tot = 0;
fill(t.begin(), t.end(), node());
}

int build(int l, int r) {
int u = ++tot;
if (l >= r) return u;
int mid = (l + r) >> 1;
t[u].l = build(l, mid);
t[u].r = build(mid+1, r);
return u;
}

int change(int pre, int l, int r, int x) {
int u = ++tot;
t[u] = t[pre];
t[u].sum = t[pre].sum + 1;
if (l >= r) return u;

int mid = (l + r) >> 1;
if (x <= mid) t[u].l = change(t[pre].l, l, mid, x);
else t[u].r = change(t[pre].r, mid + 1, r, x);

return u;
}

int query(int u, int v, int l, int r, int K) {
if (l == r) return l;
int cnt = t[t[v].l].sum - t[t[u].l].sum;
int mid = (l + r) >> 1;

if (K <= cnt) return query(t[u].l, t[v].l, l, mid, K);
else return query(t[u].r, t[v].r, mid+1, r, K-cnt);
}
};

const int maxn = 100000 + 10;
wsegTree wseg(maxn);
int n, m, root[maxn], a[maxn], b[maxn];

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &m);

map<int, int> M;
int idx = 0;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), M[a[i]] = 0;
for (auto &x : M) {
x.second = ++idx, b[idx] = x.first;
}

for (int i = 1; i <= n; i++) {
root[i] = wseg.change(root[i-1], 1, idx, M[a[i]]);
}

while (m--) {
int u, v, k;
scanf("%d%d%d", &u, &v, &k);
int res = wseg.query(root[u-1], root[v], 1, idx, k);
printf("%d\n", b[res]);
}
}

区间内小于等于 k 的数有多少

HDU4417
Super Mario
HDU4417

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
class wsegTree {
public:
struct node {
int l, r;
int sum;
};

int n;
int tot;
vector<node> t;

wsegTree() = default;
wsegTree(int _n) : n(_n) {
assert(n > 0);
tot = 0;
t.resize(n * 20);
}
void clear() {
tot = 0;
fill(t.begin(), t.end(), node());
}

int build(int l, int r) {
int u = ++tot;
if (l >= r) return u;
int mid = (l + r) >> 1;
t[u].l = build(l, mid);
t[u].r = build(mid+1, r);
return u;
}

int change(int pre, int l, int r, int x, int v) {
// find [l, r] = [x, x]
int u = ++tot;
t[u] = t[pre];
t[u].sum = t[pre].sum + v;
if (l >= r) return u;
int mid = (l + r) >> 1;
if (x <= mid) t[u].l = change(t[pre].l, l, mid, x, v);
else t[u].r = change(t[pre].r, mid+1, r, x, v);
return u;
}
int query(int i, int j, int l, int r, int k) {
if (l >= r) return t[j].sum - t[i].sum;
int res = 0, mid = (l + r) >> 1;
if (k <= mid) res = query(t[i].l, t[j].l, l, mid, k);
else {
res += t[t[j].l].sum - t[t[i].l].sum;
res += query(t[i].r, t[j].r, mid + 1, r, k);
}
return res;
}
};

const int maxn = 100000 + 5;
wsegTree wseg(maxn);
int a[maxn], b[maxn], n, m, root[maxn];

int main() {
freopen("input.txt", "r", stdin);
int T;
cin >> T;
int kase = 0;
while (T--) {
printf("Case %d:\n", ++kase);
wseg.clear();
memset(root, 0, sizeof root);
scanf("%d%d", &n, &m);
map<int, int> M;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), M[a[i]] = 0;
int idx = 0;
for (auto &x : M) {
x.second = ++idx, b[idx] = x.first;
}

// build weight segment tree
for (int i = 1; i <= n; i++) root[i] = wseg.change(root[i-1], 1, idx, M[a[i]], 1);

// then solve
while (m--) {
int u, v, h;
scanf("%d%d%d", &u, &v, &h);
u++, v++;
int k = upper_bound(b+1, b+1+idx, h) - b;
k--;
if (k == 0) {
puts("0");
continue;
}
int res = wseg.query(root[u-1], root[v], 1, idx, k);
printf("%d\n", res);
}
}
}

统计区间有多少不同数字

Sequence 2
HDU5919

给定序列{a1,a2,,an}\{a_1, a_2, \cdots , a_n\}

  • 询问区间[L,R][L, R] 中有kk 个不同的数,并且求第k2\lceil \frac{k}{2} \rceil 大,很容易想到用主席树维护
    对于aia_i,主席树root(i)root(i) 表示区间[1i][1\cdots i] 中有多少个不同的数
  • 主席数叶子节点分别为[1,1],[2,2],,[n,n][1, 1], [2, 2], \cdots, [n, n]
  • 问题是,要求每个数只能出现一次,不能重复计数,并且每个数只记录第一次出现的位置
    结合线段树可以单调修改的特性,可以设计出如下算法
    • n1n \to 1 倒序循环序列,并且使用一个map\textbf{map} 来维护每一个数出现的位置
      对于某个ii,如果map[ai]>0\textbf{map}[a_i] > 0,那么不需要往主席树中添加出现次数
      否则的话,map[ai]=0\textbf{map}[a_i] = 0,执行主席树单点增加root(i)change(root(i+1),i,1)root(i) \leftarrow \textbf{change}(root(i+1), i, 1)
      然后令map[ai]=i\textbf{map}[a_i] = i
      (类似于树状数组单点增加,在下标为ii 的位置,让权值+1+1)
    • 还有一个问题,题中要求维护第一次出现的位置,这其实也很好解决
      对于某个位置ii,若j=map[ai]>0j = \textbf{map}[a_i] > 0,对于主席树root(i)root(i),在下标为jj 的位置1-1 即可
      具体来说,root(i)change(root(i+1),i,1)root(i) \leftarrow \textbf{change}(root(i+1), i, 1),然后root(i)change(root(i),j,1)root(i) \leftarrow \textbf{change}(root(i), j, -1)
      最后更改map[ai]i\textbf{map}[a_i] \leftarrow i
  • 对于每个询问,查询[L,R][L, R] 中有多少个不同的元素,对于主席树root(L)root(L),它不含有区间[1L1][1\cdots L-1] 的信息
    而只包括区间[L,n][L, n] 的信息,具体来说,对于主席树root(L)root(L),它的根节点表示区间为[1,n]=[L,n][1, n] = [L, n]
    在主席树root(L)root(L) 上执行标准的线段树查询区间和,找到表示[L,R][L, R] 区间的节点
    返回节点维护的信息K=sumK=sum 即可
  • 如何求第K/2\lceil K/2 \rceil 个元素?只要在主席树root(L)root(L) 中执行二分即可
    具体来说,query(root(L),1,n,K/2)\textbf{query}(root(L), 1, n, \lceil K/2 \rceil)
    左子树元素个数K\geqslant K,递归左子树,否则递归查询右子树的第KcntK-cnt 个元素
    • 细节,这里对主席树root(L)root(L) 根节点区间[1,n]=[L,n][1, n] = [L, n] 递归即可
      不必考虑[L,R][L,n][L, R] \subseteq [L, n],因为[L,R][L, R] 总共才KK 个元素
      查询第K/2\lceil K/2 \rceil 个元素,不会用到[R+1n][R+1\cdots n] 这些数

另外,本例不需要对序列进行离散化,什么时候需要什么时候不需要呢?

  • 对于区间第KK 大,对于AiA_i,实际上我们执行了C[Ai]+=1C[A_i] += 1 的操作
    相当于第ii 个主席树,叶节点[l,r]=[Ai,Ai][l, r] = [A_i, A_i]+1+1
    表示AiA_i 这个数,在A[1i]A[1\cdots i] 前缀序列中,出现了11
    我们的目的是询问部分和:其中Ai<Aj, (C[Ai,Ai]C[Aj,Aj])A_i < A_j, \ \sum (C[A_i, A_i] \to C[A_j, A_j]) 恰好等于KKjj
    每一个叶节点表示[Ai,Ai][A_i, A_i],需要离散化
  • 本例呢?本例统计的是有多少个数
    具体来说,对于某个位置iiAiA_i 第一次出现 (之前的位置j<i,Aij < i, A_i 都没出现过)
    我们认为ii 这个位置对答案贡献了11,在[l,r]=[i,i][l, r] = [i, i]+1+1
    叶节点表示位置信息[i,i][i, i],不需要离散化
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
const int maxn = 200000 + 10;
int a[maxn], n, m, root[maxn];

class wsegTree {
public:
struct node {
int l, r;
int sum;
};
int n;
int tot;
vector<node> t;

wsegTree() = default;
wsegTree(int _n) : n(_n) {
assert(n > 0);
tot = 0;
t.resize(n * 36);
}
void clear() {
tot = 0;
fill(t.begin(), t.end(), node());
}

int change(int pre, int l, int r, int x, int v) {
int u = ++tot;
t[u] = t[pre];
t[u].sum = t[pre].sum + v;

if (l >= r) return u;
int mid = (l + r) >> 1;
if (x <= mid) t[u].l = change(t[pre].l, l, mid, x, v);
else t[u].r = change(t[pre].r, mid+1, r, x, v);

return u;
}

int query(int u, int l, int r, const int li, const int ri) {
if (li <= l && r <= ri) return t[u].sum;
int mid = (l + r) >> 1;
int ans = 0;
if (li <= mid) ans += query(t[u].l, l, mid, li, ri);
if (ri > mid) ans += query(t[u].r, mid+1, r, li, ri);
return ans;
}

int query(int u, int l, int r, int k) {
if (l >= r) return l;
int mid = (l + r) >> 1;
int cnt = t[t[u].l].sum;

if (cnt >= k) return query(t[u].l, l, mid, k);
else return query(t[u].r, mid+1, r, k-cnt);
}
};

wsegTree wseg(maxn);

int main() {
freopen("input.txt", "r", stdin);
int T;
scanf("%d", &T);
int kase = 0;
while (T--) {
printf("Case #%d:", ++kase);
// init
memset(root, 0, sizeof root);
wseg.clear();

scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

// build seg tree
map<int, int> M;
for (int i = n; i >= 1; i--) {
root[i] = wseg.change(root[i+1], 1, n, i, 1);
if (M[a[i]]) root[i] = wseg.change(root[i], 1, n, M[a[i]], -1);
M[a[i]] = i;
}

// query
vector<int> ans(maxn, 0);
for (int i = 1; i <= m; i++) {
int l, r, li, ri;
scanf("%d%d", &l, &r);
li = min((l + ans[i-1]) % n + 1 , (r + ans[i-1]) % n + 1);
ri = max((l + ans[i-1]) % n + 1 , (r + ans[i-1]) % n + 1);
if (li > ri) swap(li, ri);

int k = wseg.query(root[li], 1, n, li, ri);
k = (k+1) / 2;
ans[i] = wseg.query(root[li], 1, n, k);
}
for (int i = 1; i <= m; i++) printf(" %d", ans[i]);
puts("");
}
}

延迟标记永久化

  • 普通线段树,对于change(L,R,d)\textbf{change}(L, R, d),即将[L,R][L, R] 区间的数都加上dd,用延迟标记
    首先找到表示[L,R][L, R] 区间的节点uu,然后修改uudatdat 信息,并且打上延迟标记
    打上延迟标记意味着区间已经修改,但延迟标记尚未下传
    具体点说,如果之后询问子区间[l,r][L,R][l, r] \subset [L, R],必须先push(u)\textbf{push}(u)
    push\textbf{push} 的过程就是将延迟标记作用于经过的子节点,即apply(u)uchild pathapply(u) \quad u \in \text{child path}
    这样在递归访问子节点的时候,路径上经过的区间都会得到修改,直到问询区间[l,r][l, r]
  • 权值线段树,可以考虑将lazy\text{lazy} 标记持久化,考虑到权值线段树change\textbf{change} 的操作是自顶向下修改
    主席树执行change(L,R,d)\textbf{change}(L, R, d) 的时候,从[1,n][L,R][1, n] \to \cdots \to [L, R] 路径上所有点表示的区间都会改变
    于是可以边递归边修改,对于路径[1,n][L,R][1, n] \to \cdots \to [L, R]所有点uu
    都执行u.dat+=d(min(ur,R)max(ul,L)+1)u.\text{dat} += d \cdot (\min(u_r, R)-\max(u_l, L) + 1)
    只要在递归终点,要修改的区间[L,R][L, R] 打上lazy\text{lazy} 标记
    注意,此时的状态是
    [1,n][L,R][1, n] \to [L, R],包括[L,R][L, R] 所有区间都已经修改完毕,但延迟标记尚未下传到[L,R][L, R] 的子区间中
  • 如果[L,R][L, R]lazy\text{lazy} 标记,当且仅当询问子区间[li,ri][L,R][li, ri] \subset [L, R] 的时候,才下传延迟标记
    这里可以在递归的时候,加入一个参数addadd
    query(u,li,ri,add)\textbf{query}(u, li, ri, add)初始调用的时候add=0,query(u,1,n,0)add = 0, \textbf{query}(u, 1, n, 0)
    • 如果liulurrili \leqslant u_l \leqslant u_r \leqslant riuu 这个节点就为待求区间
      resu.dat+add(urul+1)res \leftarrow u.\text{dat} + add \cdot (u_r - u_l + 1)
    • 否则的话,需要递归求解uu 的子区间,addadd+u.lazyadd \leftarrow add + u.\text{lazy}
      然后考虑递归左半边和右半边,以左半边为例,res+=query(t[u].l, li,ri,add+u.lazy)res += \textbf{query}(t[u].l, \ li, ri, add + u.\text{lazy})

HDU4348
To The Moon

  • 在时间t=0t = 0 建一棵线段树,root(0)=build(1,n)root(0) = build(1, n),建树时候将叶节点数据初始化为aia_i
  • 接下来根据时间tt 建主席树,(C L R d)(C \ L \ R \ d) 实际上就是roott=change(roott1,l,r,d)root_t = \textbf{change}(root_{t-1}, l, r, d) 操作
  • 对于询问(Q L R)(Q \ L \ R),直接在当前时间点root(t)root(t) 执行查询,历史时间点就查询root(t)root(t')
  • (B t)(B \ t),清空时间tt 以后的操作,只要把动态开点的指针totroot(t+1)tot \leftarrow root(t+1) 即可
    或者将当前的时间戳设为tttcurtt_{\text{cur}} \leftarrow t
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
113
114
115
const int maxn = 1e5 + 10;
int n, m, root[maxn];
ll a[maxn];

class wsegTree {
public:
struct node {
int l, r;
ll lazy, sum;
};
int n;
int tot;
vector<node> t;

wsegTree() = default;
wsegTree(int _n) : n(_n) {
assert(n > 0);
tot = 0;
t.resize(n * 25);
}
void clear() {
tot = 0;
fill(t.begin(), t.end(), node());
}

int build(int l, int r) {
int u = ++tot;
if (l >= r) {
t[u].sum = a[l];
return u;
}
int mid = (l + r) >> 1;
t[u].l = build(l, mid);
t[u].r = build(mid+1, r);
t[u].sum = t[t[u].l].sum + t[t[u].r].sum;
return u;
}

int change(int pre, int l, int r, const int li, const int ri, ll v) {
int u = ++tot;
t[u] = t[pre];
t[u].sum += v * (min(r, ri) - max(l, li) + 1);

if (li <= l && r <= ri) {
t[u].lazy += v;
return u;
}

int mid = (l + r) >> 1;
if (li <= mid) t[u].l = change(t[pre].l, l, mid, li, ri, v);
if (ri > mid) t[u].r = change(t[pre].r, mid+1, r, li, ri, v);

return u;
}

ll query(int u, int l, int r, const int li, const int ri, ll add) {
if (li <= l && r <= ri) {
ll res = t[u].sum + add * (r-l+1);
return res;
}
add += t[u].lazy;
int mid = (l + r) >> 1;
ll res = 0;
if (li <= mid) res += query(t[u].l, l, mid, li, ri, add);
if (ri > mid) res += query(t[u].r, mid+1, r, li, ri, add);
return res;
}
};

wsegTree wseg(maxn);

int main() {
freopen("input.txt", "r", stdin);
while (~scanf("%d%d", &n, &m)) {
// init
wseg.clear();
memset(root, 0, sizeof root);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);

// build
root[0] = wseg.build(1, n);
// m queries
int t = 0;
while (m--) {
char str[2];
scanf("%s", str);

if (str[0] == 'Q') {
int li, ri;
scanf("%d%d", &li, &ri);
//debug(li);
ll res = wseg.query(root[t], 1, n, li, ri, 0);
printf("%lld\n", res);
}
if (str[0] == 'C') {
t++;
int li, ri;
ll d;
scanf("%d%d%lld", &li, &ri, &d);
root[t] = wseg.change(root[t-1], 1, n, li, ri, d);
}
if (str[0] == 'H') {
int li, ri, ti;
scanf("%d%d%d", &li, &ri, &ti);
ll res = wseg.query(root[ti], 1, n, li, ri, 0);
printf("%lld\n", res);
}
if (str[0] == 'B') {
int ti;
scanf("%d", &ti);
t = ti;
}
}
}
}

主席树树上查询

树上查询常见的问题,给你树上任意两个节点u,vu, v,问询uvu \to v 路径上第kk 小节点是谁?权值多少?
Count On a Tree
SPOJ-COT

lca=LCA(u,v), pa=pa(lca)\text{lca} = \text{LCA}(u, v),\ pa = pa(lca)
f(u,li,ri)f(u, li, ri) 表示从root\text{root}uu 的路径上,权值落在[li,ri][li, ri] 区间内的点的个数
uvu \to v 路径上,权值落在区间[li,ri][li, ri] 的点的个数为

f(v,li,ri)+f(u,li,ri)f(pa,li,ri)f(lca,li,ri)f(v, li, ri) + f(u, li, ri) - f(pa, li, ri) - f(\text{lca}, li, ri)

可以考虑使用主席树(函数式线段树)来维护

  • 先对所有的权值进行离散化,编号为uu 的点,离散后的权值为M[au]M[a_u]

  • 设根节点为11,哨兵节点为00dfs(u,pa)\textbf{dfs}(u, pa) 遍历树,初始调用dfs(1,0)\textbf{dfs}(1, 0)

  • dfs(u,pa)\textbf{dfs}(u, pa) 的时候,root(u)change(root(pa),M[au],1)\text{root}(u) \leftarrow \textbf{change}(\text{root}(pa), M[a_u], 1)

  • 接下来就是在路径序列中执行 KQuery,对于主席树的某个节点[pl,pr][p_l, p_r],它包含权值在[u,v][u, v] 区间内的点的个数为

    • 同时递归root(v),root(u),root(lca),root(pa)\text{root}(v), \text{root}(u), \text{root}(\text{lca}), \text{root}(pa) 四棵线段树
      找到表示[pl,pr][p_l, p_r] 的节点t[u],t[v],t[lca],t[pa]t[u], t[v], t[\text{lca}], t[pa]
    • cnt(p)=t[v].sum+t[u].sumt[lca].sumt[pa].sum\text{cnt}(p) = t[v].sum + t[u].sum - t[\text{lca}].sum - t[pa].sum

    然后就是标准的二分查找,如果cnt(tp.l)K\text{cnt}(t_p.l) \geqslant K,查询pp 的左子树,否则查询右子树第Kcnt(tp.l)K-\text{cnt}(t_p.l) 个元素
    直到叶节点l=rl = r,返回ll

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
class Graph {
public:
int tot = 1;
int n;
vector<int> head, ver, ne;

Graph() = default;
Graph(int _n) : n(_n) {
tot = 1;
head.resize(n), ver.resize(n<<1), ne.resize(n<<1);
}
void clear() {
tot = 1;
fill(head.begin(), head.end(), 0);
}
void add(int a, int b) {
ver[++tot] = b, ne[tot] = head[a], head[a] = tot;
}
};

const int maxn = 100000 + 10;
const int LOG = 31;
int idx, m, a[maxn], b[maxn], root[maxn], dep[maxn], f[maxn][LOG+1];
map<int, int> M;
Graph G(maxn);
int n = 0;

class wsegTree {
public:
struct node {
int l, r;
int sum;
};
int n;
int tot;
vector<node> t;

wsegTree() = default;
wsegTree(int _n) : n(_n) {
assert(n > 0);
tot = 0;
t.resize(n << 5);
}
void clear() {
tot = 0;
fill(t.begin(), t.end(), node());
}

int change(int pre, int l, int r, int x, int v) {
int u = ++tot;
t[u] = t[pre];
t[u].sum = t[pre].sum + v;

if (l >= r) return u;
int mid = (l + r) >> 1;
if (x <= mid) t[u].l = change(t[pre].l, l, mid, x, v);
else t[u].r = change(t[pre].r, mid+1, r, x, v);

return u;
}

int query(int u, int v, int lca, int fa, int l, int r, int k) {
if (l >= r) return l;

int cnt = t[t[u].l].sum + t[t[v].l].sum - t[t[lca].l].sum - t[t[fa].l].sum;
int mid = (l + r) >> 1;
if (cnt >= k) return query(t[u].l, t[v].l, t[lca].l, t[fa].l, l, mid, k);
else return query(t[u].r, t[v].r, t[lca].r, t[fa].r, mid+1, r, k-cnt);
}
};

wsegTree wseg(maxn);

void dfs(int u, int pa) {
f[u][0] = pa, dep[u] = dep[pa] + 1;
for (int j = 1; j <= LOG; j++) f[u][j] = f[f[u][j-1]][j-1];
root[u] = wseg.change(root[pa], 1, n, M[a[u]], 1);

for (int i = G.head[u]; i; i = G.ne[i]) {
int v = G.ver[i];
if (v == pa) continue;
dfs(v, u);
}
}

int LCA(int x, int y) {
if (dep[x] > dep[y]) swap(x, y);
for (int i = LOG; i >= 0; i--) {
if (dep[f[y][i]] >= dep[x]) y = f[y][i];
}
if (y == x) return y;
for (int i = LOG; i >= 0; i--) {
if (f[y][i] != f[x][i]) y = f[y][i], x = f[x][i];
}
return f[x][0];
}

int main() {
freopen("input.txt", "r", stdin);
memset(root, 0, sizeof root);
memset(dep, 0, sizeof dep);
memset(f, 0, sizeof f);
M.clear();
// get graph
scanf("%d%d", &idx, &m);
for (int i = 1; i <= idx; i++) scanf("%d", &a[i]), M[a[i]] = 0;

n = 0;
for (auto &u : M) {
u.second = ++n, b[n] = u.first;
}

for (int i = 1; i <= idx-1; i++) {
int u, v;
scanf("%d%d", &u, &v);
G.add(u, v), G.add(v, u);
}

// dfs
dfs(1, 0);

// query
int res = 0;
while (m--) {
int u, v, k;
scanf("%d%d%d", &u, &v, &k);
int lca = LCA(u, v), fa = f[lca][0];
//debug(fa);
int res = wseg.query(root[u], root[v], root[lca], root[fa], 1, n, k);
printf("%d\n", b[res]);
}
}