1. 首页
  2. 文章中心
  3. ACM ---- 数据结构

划分树知识点详解

110 阅读 0 评论
我是靠谱客的博主 明理龙猫，这篇文章主要介绍划分树知识点详解，现在分享给大家，希望可以做个参考。

一、介绍概念

1、

划分树是一种基于线段树的数据结构。

主要用于  快速求出(在log(n)的时间复杂度内）序列区间的区间内的第k大数。

第 k 大数：

在已经排序好的序列中，找 第 k 的数字就是 第 k 大数字

例如 ： 1 2 3 4 5  

             第 3 大数字是  3

             4 3 6 5 1

             第 2 大数字是 3

2、

划分树的定义就是对整体的区间进行划分，把相对于原来序列中较小的值放在左子树，较大的放在右子树，最后按照它的性质进行查询以此找到要查询的区间里的第k大数。

例图（图是偷的~~~） 
这里写图片描述

 

二、具体步骤

1.建树 

（1）步骤

建树是一个不停递归的过程 
第一步：

首先我们要根据排序后的数组找到当前层数的中值（中值即中位数：注意，是中位数，不是中间的数）

                                            中值 = sorted [ ( left + mid) / 2 ]

将没有排序的序列（即输入的原序列）里面的数这样安排：

小于中位数的放进左子树，大于等于中位数的放进右子树

当然了，这是针对中值只有唯一一个时候的做法，一会再说多个中值应该怎么处理。

第二步：

对于每一个子区间，我们都采用第一步的方法去划分，直到左右区间相等的时候，即为终止递归的条件。

第三步：

在我们向左子树里放数的时候，我们还要统计出区间 [left,right ] 里有多少个数进入了左子树（这个主要用于查询操作）。

在划分树的时候，有几点需要注意： 


1.建树是分层的，所以我们要用二维数组去存储，第一维只需要20就够了，因为100000的数据量的话，它的层数为logN。 
2.划分的标准是中值，在第一步里已经特别强调过。 
3.划分的数永远存放在它的下一层，为什么呢？下面举个例子模拟一下过程就知道了。

那么下面先列出我们要用到的数组：

复制代码
1
2
3
4
5
6
7
const int MAXL(1e5);
int tree[level][MAXL+50];     //第一维代表当前的树的层数，
                              //第二维代表这一层经过划分后的序列值
int toLeft[level][MAXL+50];   //第一维代表当前的树的层数，
                              //第二维代表当前层区间[left,right]进入左子树的数目
int sorted[MAXL+50];          //将初始序列排序后的数组
                              //  level 的值 取 20 即可

按照图中给出的原始序列为

复制代码
1
4 2 5 7 1 8 3 6

 

排序后的序列为

复制代码
1
1 2 3 4 5 6 7 8

 

那么我们tree [ 0 ]保存的应该是原始序列 

并且得到toLeft [ 0 ] 的序列

复制代码
1
2
3
tree[0]   = 4 2 5 7 1 8 3 6
toLeft[0] = 1 2 2 2 3 3 4 4 // 当前区间进入到下一层左子树的数目

 

再次强调一遍 
toLeft [ i ] [ j ] 存的是 第 i 层，当前划分区间【 left , right 】里进入左子树的个数 
至于为什么要这么存，一会说查询的时候就知道了。

（2）模拟一下划分过程 


首先是第一层，找到中值4 （中值= sorted[ ( left + mid) / 2 ] ） 
那么tree [ 1 ] 和toLeft [ 1 ] 应该是

复制代码
1
2
3
tree[1]   =   4 2 1 3      5 7 8 6   // 第一层存的数
toLeft[1] =   0 1 2 2      1 1 1 2  //  由第 1 层进入到第 2 层的左子树的数目
          //  一开始初始化 为 0

 

可能这里有人注意到问题了，为什么把4划分到了左区间？上面不是说大于等于中值的划分到右区间吗？ 别急-

第二层，分别对左子树和右子树按照上述的方法划分

复制代码
1
2
tree[2]   =   2 1    4 3      5 6    7 8
toLeft[2] =   0 1    0 1      1 1    1 1

在这里再啰嗦地解释一下这一组的 toLeft 数组 
很明显这一组的 2 1 4 3 5 6 7 8 
分别在左 右 左 右 子树 
那么对于左子树里的 2 1这个小区间，进入下一层左子树的数分别为 0 1  （ 1 进入左子树，2不进入）
对于右子树 4 3 这个小区间，进入下一层左子树的数分别为 0 1 
… 
… 
第三层

复制代码
1
2
tree[3]   =   1 2 3 4 5 6 7 8
toLeft[3] =   0 0 0 0 0 0 0 0

 

（3）、特殊处理

下面开始说另外一个要注意的问题：有多个中值怎么办？？？

因为我们要使得左右区间的数量尽可能的均等 
所以在这里，我们用一种特殊的处理方法。

在还没有进行划分之前，我们先假设  中值左边的数据都小于中值
即        设置一个  suppose = mid - left + 1 （初值）
如果当前的数  小于中值,就使        suppose减一

即

复制代码
1
2
if( tree[level][i]< sorted[mid] ）
    suppose--;

 

如果结果如我们假设的那样，那么suppose最后一定等于1，（因为留下了一个中值的位置）

否则，就说明中值的数量不唯一

那么在下面进行的时候，如果还剩   suppose>1，就先把中值放在左子树，直到 suppose为0，如果仍还有中值，就把剩下的放进右子树
通过这样操作，就能均分左右子树了。

再举个例子增深理解： 
3 3 4 4 4 5 7  

sorted[ 4 ] = 4
中值为4，左子树要放 4个（(1+7)/2），右子树放3个 
处理后的suppose为 2 
那么遇到第一个4，放进左子树，suppose=1; 
遇到第二个4，放进左子树，suppose=0； 
遇到第三个 4,这时suppose已经等于 0，所以放进右子树。

（4） 建树CODE：

复制代码
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
void Build_tree(int level,int left,int right)    //level为当前层
{
    if(left==right)                              //左右区间相等为终止条件
        return ;
    int mid=(left+right)>>1; 
    int suppose=mid-left+1;                      //设定suppose的初值
    for(int i=left; i<=right; i++)
        if(tree[level][i]<sorted[mid])           //处理suppose
            suppose--;
    int subLeft=left,subRight=mid+1;             //进入下层左右子树的下标
    for(int i=left; i<=right; i++)
    {
        if(i==left)                              //初始化
            toLeft[level][i]=0;
        else                                     //初始化
            toLeft[level][i]=toLeft[level][i-1];
        if(tree[level][i]<sorted[mid]||tree[level][i]==sorted[mid]&&suppose>0)
        {                 
                  //这就是上面说的处理多个中值的情况，放在一起了，进入左子树

            tree[level+1][subLeft++]=tree[level][i]; //将数放在下一层
            toLeft[level][i]++;                  //进入左子树的数目+1
            if(tree[level][i]==sorted[mid])
                suppose--;                       //继续处理suppose
        }
        else                                     //进入右子树
            tree[level+1][subRight++]=tree[level][i];
    }
    Build_tree(level+1,left,mid);               //递归建左子树
    Build_tree(level+1,mid+1,right);            //递归建右子树
}

 

2、查询

（1）、确定左子树右子树

假设初始大区间为【left , right】，要查询的区间为【qLeft , qRight】 
现在要查询区间【qLeft , qRight】的第k大数

思路：

先判断【qLeft , qRight】在【left , right】的哪个子树中，然后找出对应的小区间和  k ，然后递归查找，直到小区间qLeft==qRight  时为止。

那如何解决这个问题呢？

这时候前面记录的进入左子树的元素个数就派上用场了。通过之前的记录可以知道，

在区间【left , qLeft】中有   toLeft [ level ] [ qLeft - 1 ]  个元素进入了左子树，记它为 lef

同理，在区间【left , qRight】中有   toLeft [ level ] [ qRight ] 个元素进入了左子树，记它为rig ，

           所以在区间【qLeft , qRight】之间就有 rig - lef 个元素进入了左子树，记为 toLef。

           如果 toLef>= k ，说明 第 k 大元素肯定进入了左子树，那么就进入左子树查找，否则进入右子树查找。

（2）、确定小区间的问题：

 如果进入的是左子树，那么小区间就应该是 
【 left +( [ left , qLeft-1] )进入左子树的数目，left +（ [ left , qRight ] ）进入左子树的数目-1】 
即：【 left + lef , left + lef + tolef-1 】,并且，这时候k的值不用变化

复制代码
1
2
3
4
5
6
7
8
 if(k<=toLef)//进入左子树
 {
        int newLeft=left+lef;           // 左端点
        int newRight=left+lef+toLef-1; //  右端点
  //或  int  newRight = newLeft + tolef -1 ;
        return Query(level+1,newLeft,newRight,left,mid,k); // 递归查询
 }

 

如果进入的是右子树，那么小区间就应该是 
【 mid +( [ left,qLeft-1] )进入右子树的数目+1，mid +（ [ left,qRight ] ）进入右子树的数目】 
即：【 mid + qLeft - left -lef + 1 , mid + qRight - left - toLef - lef + 1 】 
同时，这里的k要发生变化，变为k-（【qLeft , qRight】进入左子树的元素个数） 
                                         即 k-toLef

例如：求第3 大，有两个元素进入到左子树中，那么就变成去求 右子树中 第 1大的数字

其中  mid = ( left + right ) / 2

这里的区间式子很长，需要仔细思考。

下面举个例子（又是偷的图~~~） 
这里写图片描述

（3）、查询的 CODE

复制代码
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
int Query(int level,int qLeft,int qRight,int left,int right,int k) // 查询 
{
    int mid=(left+right)>>1;                       // 求中值
    if(qLeft==qRight)                              // 递归终止条件
        return tree[level][qLeft];
    int lef;     // 代表的是 [left,qleft-1] 进入左子树的数目的数量

    int toLef;   // 代表的是 [left,qright] 进入左子树的数目的数量
  
    if(qLeft==left）        // 如果从大区间的左端点开始查
        lef=0,toLef=toLeft[level][qRight];
  
    else
        lef=toLeft[level][qLeft-1],toLef=toLeft[level][qRight]-lef;
    
    if(k<=toLef)           //  进入左子树
    {
        int newLeft=left+lef;
        int newRight=left+lef+toLef-1;
        return Query(level+1,newLeft,newRight,left,mid,k);
    }
    else                   //  进入右子树
    {
        int newLeft=mid+qLeft-left-lef+1;
        int newRight=mid+qRight-left-toLef-lef+1;
        return Query(level+1,newLeft,newRight,mid+1,right,k-toLef);
    }
}

 

 

三、CODE

po 两个例题

poj 2104

hdu 2665 

CODE:（针对 poj 2104 的代码）

复制代码
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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<utility>
#include<list>
#include<algorithm>
#define max(a,b)   (a>b?a:b)
#define min(a,b)   (a<b?a:b)
#define swap(a,b)  (a=a+b,b=a-b,a=a-b)
#define memset(a,v)  memset(a,v,sizeof(a))
#define X (sqrt(5)+1)/2.0  //Wythoff
#define Pi acos(-1)
#define e  2.718281828459045
#define eps 1.0e-8
using namespace std;
typedef long long int LL;
typedef pair<int,int>pa;
const int MAXL(1e5);
const int INF(0x3f3f3f3f);
const int mod(1e9+7);
int dir[4][2]= {{-1,0},{1,0},{0,1},{0,-1}};
int tree[20][MAXL+50];
int toLeft[20][MAXL+50];
int sorted[MAXL+50];
void Build_tree(int level,int left,int right)  // 建树
{ 
    if(left==right)
        return ;
    int mid=(left+right)>>1;
    int suppose=mid-left+1;
    for(int i=left; i<=right; i++)
        if(tree[level][i]<sorted[mid])
            suppose--;
    int subLeft=left,subRight=mid+1;
    for(int i=left; i<=right; i++)
    {
        if(i==left)
            toLeft[level][i]=0;
        else
            toLeft[level][i]=toLeft[level][i-1];
        if(tree[level][i]<sorted[mid]||tree[level][i]==sorted[mid]&&suppose>0)
        {
            tree[level+1][subLeft++]=tree[level][i];
            toLeft[level][i]++;
            if(tree[level][i]==sorted[mid])
                suppose--;
        }
        else
            tree[level+1][subRight++]=tree[level][i];
    }
    Build_tree(level+1,left,mid);
    Build_tree(level+1,mid+1,right);
}

int Query(int level,int qLeft,int qRight,int left,int right,int k) // 查询 
{
    int mid=(left+right)>>1;
    if(qLeft==qRight)
        return tree[level][qLeft];
    int lef;
    int toLef;
    if(qLeft==left)
        lef=0,toLef=toLeft[level][qRight];
    else
        lef=toLeft[level][qLeft-1],toLef=toLeft[level][qRight]-lef;
    if(k<=toLef)
    {
        int newLeft=left+lef;
        int newRight=left+lef+toLef-1;
        return Query(level+1,newLeft,newRight,left,mid,k);
    }
    else
    {
        int newLeft=mid+qLeft-left-lef+1;
        int newRight=mid+qRight-left-toLef-lef+1;
        return Query(level+1,newLeft,newRight,mid+1,right,k-toLef);
    }
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&tree[0][i]);
        sorted[i]=tree[0][i];
    }
    sort(sorted+1,sorted+n+1);
    Build_tree(0,1,n);
    while(m--)
    {
        int ql,qr,k;
        scanf("%d%d%d",&ql,&qr,&k);
        int ans=Query(0,ql,qr,1,n,k);
        cout<<ans<<endl;
    }
}

 

附：

做题的过程中发现了toLeft数组的另一种存法

下面的模板代码对于

toLeft【i】【j】  存的是第 i 层 1到 j 进入左子树的元素个数 

复制代码
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX_SIZE 100005  
int sorted[MAX_SIZE];     //已经排好序的数据  
int toleft[25][MAX_SIZE];  
int tree[25][MAX_SIZE];  
void build_tree(int left, int right, int deep)   
{  
    int i;  
    if (left == right) return ;  
    int mid = (left + right) >> 1;  
    int same = mid - left + 1;          //位于左子树的数据  
    for (i = left; i <= right; ++i) {   //计算放于左子树中与中位数相等的数字个数  
        if (tree[deep][i] < sorted[mid]) {  
            --same;  
        }  
    }  
    int ls = left;      // 下一层左子树的端点
    int rs = mid + 1;   // 下一层右子树的端点
    for (i = left; i <= right; ++i) {  
        int flag = 0;  
        if ((tree[deep][i] < sorted[mid]) || (tree[deep][i] == sorted[mid] && same > 0)) {  
            flag = 1;  
            tree[deep + 1][ls++] = tree[deep][i];  
            if (tree[deep][i] == sorted[mid])  
                same--;  
        } else {  
            tree[deep + 1][rs++] = tree[deep][i];  
        }  
        toleft[deep][i] = toleft[deep][i - 1]+flag;   // 相当于递推的过程，等于上一个过程 加 1 （进入 左子树）或者 加 0（进入右子树）
    }  
    build_tree(left, mid, deep + 1);  
    build_tree(mid + 1, right, deep + 1);  
}  

int query(int left, int right, int k, int L, int R, int deep)  
{  
    if (left == right)  
        return tree[deep][left];  
    int mid = (L + R) >> 1;  
    int x = toleft[deep][left - 1] - toleft[deep][L - 1];//位于[L,left]的放于左子树中的数字个数  
    int y = toleft[deep][right] - toleft[deep][L - 1];//到[L,right]位于左子树的个数  
    int ry = right - L - y;  // 到right右边为止位于右子树的数字个数  
    int cnt = y - x;        //  [left,right]区间内放到左子树中的个数  
    int rx = left - L - x;//    left左边放在右子树中的数字个数  
    if (cnt >= k) {  
        //printf("sss %d %d %dn", xx++, x, y);  
        return query(L + x, L + y - 1, k, L, mid, deep + 1);
        // 因为x不在区间内 所以没关系 所以先除去，从L+x开始，然后确定范围
    }  
    else {  
        //printf("qqq %d %d %dn", xx++, x, y);  
        return query(mid + rx + 1, mid + 1 + ry, k - cnt, mid + 1, R, deep + 1); 
        //同理 把不在区间内的 分到右子树的元素数目排除，确定范围 
    }  
}  
int main()  
{  
    int m, n;  
    int a, b, k;  
    int i;  
    while (scanf("%d%d", &m, &n) == 2) {  
        for (i = 1; i <= m; ++i) {  
            scanf("%d", &sorted[i]);  
            tree[0][i] = sorted[i];  
        }  
        sort(sorted + 1, sorted + 1 + m);  
        build_tree(1, m, 0);  
        for (i = 0; i < n; ++i) {  
            scanf("%d%d%d", &a, &b, &k);  
            printf("%dn", query(a, b, k, 1, m, 0));  
        }  
    }  
    return 0;  
}

 

最后

以上就是明理龙猫最近收集整理的关于划分树知识点详解的全部内容，更多相关划分树知识点详解内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(73)

相关文章

划分树学习（poj 2104，hdu 3473）
划分树学习（poj 2104，hdu 3473）
POJ2104：划分树求区间第k小
POJ2104：划分树求区间第k小
区间第K大(划分树)
区间第K大(划分树)
（数据结构）划分树（查询区间第 k 大）和题库
（数据结构）划分树（查询区间第 k 大）和题库
划分树知识点详解
划分树知识点详解
划分树的用法(一)：查询区间第K大值值（poj2104）
划分树的用法(一)：查询区间第K大值值（poj2104）
划分树---hdu4417---区间查找(不)大于h的个数 Super Mario
划分树---hdu4417---区间查找(不)大于h的个数 Super Mario
【划分树】求区间K大数
【划分树】求区间K大数

评论列表共有 0 条评论

立即
投稿
返回
顶部