划分树 | Kyons'Blog 




 
 
 
 



 
 



划分树

如题:POJ2014
给定一$n$个元素的数组,每次查询$[l,r]$区间内从小到大第k个数.
朴素解法为将数组$[l,r]$内的数排序,然后选择第$k$个即可.最坏情况$O(m*n)$.
这个时候,就需要更好的数据结构,划分树/归并树.

定义

1
原数组为${4,2,5,7,1,8,3,6}$,在每次划分左右子树时的中值,都用红色表明.小于中值的进入左子树,大于中值的进入右子树.
观察我们发现,每一层都是数组$n$,只不过顺序有了变化.而对于$log2(1e9)$这个数,也不过$20$.所以我们定义一个$tree[20][n]$的数组,用来存树.

1
2
//toleft稍后再讲
int tree[20][MAXN], sorted[MAXN], toleft[20][MAXN];

建树

我们定义一个数组$toleft[20][MAXN]$,其指在某数的左边所有进入左子树的数的个数.
toleft数组

1
2
3
4
5
6
7
8
9
10
11
12
第一次划分
[4,2,5,7,1,8,3,6]
[1,2,2,2,3,3,4,4] 看i-th前面有多少个数进入左子树.
第二次划分
[4,2,1,3] [5,7,8,6]
[0,1,2,2] [1,1,1,2]
第三次划分
[2,1][4,3][5,6][7,8]
[0,1][0,1][1,1][1,1]
第四次划分
[1][2][3][4][5][6][7][8]
[0][0][0][0][0][0][0][0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void built(int l, int r, int dep)
{
if (l == r)
return;
int mid = (l + r) >> 1, same = mid - l + 1;
for (int i = l; i <= r; i++) //same值指相同的中值
if (tree[dep][i] < sorted[mid])
same--;
int lpos = l, rpos = mid + 1;
for (int i = l; i <= r; i++) { //将[l,r]内的数划分
if (tree[dep][i] < sorted[mid])
tree[dep + 1][lpos++] = tree[dep][i];
else if (tree[dep][i] == sorted[mid] && same > 0) {
tree[dep + 1][lpos++] = tree[dep][i];
same--;
}
else
tree[dep + 1][rpos++] = tree[dep][i];
toleft[dep][i] = toleft[dep][l - 1] + lpos - l; //记下当前数的toleft值
}
built(l, mid, dep + 1);
built(mid + 1, r, dep + 1);
}

查询

类似于线段树的单点查询
只需要考虑一个不等式
$toleft[dep][r] - toleft[dep][l - 1]\leq k$
如果成立,说明这个数被划进了左子树.那么大区间$[L,(L+R)>>1]$,小区间$[l,r]$变为
$$[L + toleft[dep][l - 1] - toleft[dep][L - 1],newl + cnt - 1]$$
如果
$$toleft[dep][r] - toleft[dep][l - 1]<k$$
那么,这个数就被划进了右子树,那么大区间变为$[(L+R)>>1+1,R]$,小区间变为
$$[newr - (r - l - cnt),r + toleft[dep][R] - toleft[dep][r]]$$.
这样不断递归,当小区间$l==r$时,便确定了从小到大第$k$个数是几.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int query(int L, int R, int l, int r, int dep, int k)
{
if (l == r)
return tree[dep][l];
int mid = (L + R) >> 1;
int cnt = toleft[dep][r] - toleft[dep][l - 1];
if (cnt >= k) {
int newl = L + toleft[dep][l - 1] - toleft[dep][L - 1];
int newr = newl + cnt - 1;
return query(L, mid, newl, newr, dep + 1, k);
}
else {
int newr = r + toleft[dep][R] - toleft[dep][r];
int newl = newr - (r - l - cnt);
return query(mid + 1, R, newl, newr, dep + 1, k - cnt);
}
}

完整代码

当想查询从大到小第$k$个数,则将

(tree[dep][i] < sorted[mid])```改为```if (tree[dep][i] > sorted[mid])```,```sort(sorted + 1, sorted + n + 1);```改为从大到小排序即可
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

```cpp
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<string.h>
#include<map>
using namespace std;
typedef unsigned long long ull;
const int MAXN = 1e5 + 10;

int tree[20][MAXN], sorted[MAXN], toleft[20][MAXN];

void built(int l, int r, int dep)
{
if (l == r)
return;
int mid = (l + r) >> 1, same = mid - l + 1;
for (int i = l; i <= r; i++)
if (tree[dep][i] < sorted[mid])
same--;
int lpos = l, rpos = mid + 1;
for (int i = l; i <= r; i++) {
if (tree[dep][i] < sorted[mid])
tree[dep + 1][lpos++] = tree[dep][i];
else if (tree[dep][i] == sorted[mid] && same > 0) {
tree[dep + 1][lpos++] = tree[dep][i];
same--;
}
else
tree[dep + 1][rpos++] = tree[dep][i];
toleft[dep][i] = toleft[dep][l - 1] + lpos - l;
}
built(l, mid, dep + 1);
built(mid + 1, r, dep + 1);
}

int query(int L, int R, int l, int r, int dep, int k)
{
if (l == r)
return tree[dep][l];
int mid = (L + R) >> 1;
int cnt = toleft[dep][r] - toleft[dep][l - 1];
if (cnt >= k) {
int newl = L + toleft[dep][l - 1] - toleft[dep][L - 1];
int newr = newl + cnt - 1;
return query(L, mid, newl, newr, dep + 1, k);
}
else {
int newr = r + toleft[dep][R] - toleft[dep][r];
int newl = newr - (r - l - cnt);
return query(mid + 1, R, newl, newr, dep + 1, k - cnt);
}
}

int main()
{
int n, m;
while (cin >> n >> m) {
memset(tree, 0, sizeof(tree));
for (int i = 1; i <= n; i++) {
cin >> tree[0][i];
sorted[i] = tree[0][i];
}
sort(sorted + 1, sorted + n + 1);
built(1, n, 0);
int s, t, k;
while (m--) {
cin >> s >> t >> k;
cout << query(1, n, s, t, 0, k) << endl;
}
}
return 0;
}

练习题目

洛谷P2048


 


 
 
 





 

 


 


 

 

 

 

 
 

 

 

 //删除Valine核心代码库外链调用 //调用刚下载的本地文件以加速加载速度 //这里改为从本地加载