合并排序树（给定行范围内较小或相等的元素）-yiteyi-C++库

给定一个数组，其中每个元素都是一个按排序顺序包含整数的向量。任务是回答以下问题：

null


count(start, end, k) : Count the numbers smaller than or equal 
                       to k in range from array index 'start'
                       to 'end'.

为了方便起见，我们考虑N*N 2-D阵列，其中每行对应于整数向量。

例如：

Input : ar[][] = {{2, 4, 5},
                  {3, 4, 9}, 
                  {6, 8, 10}}

        Queries[] = (0, 1, 5)
                    (1, 2, 1)
                    (0, 2, 6)
Output : 5 
         0
         6
Count of elements (smaller than or equal to 5) from
1st row (index 0) to 2nd row (index 1) is 5.
Count of elements (smaller than or equal to 1) from
2nd row to 3nd row is 0
Count of elements (smaller than or equal to 6) from
1st row to 3nd row is 6.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

关键的想法是建立一个分段树每个节点上都有一个向量，该向量按排序顺序包含子范围的所有元素。如果我们观察这段树的结构，这和合并排序算法（这就是为什么它被称为合并排序树）

                     // C++ program to count number of smaller or                   
                     // equal to given number and given row range.                   
                     #include<bits/stdc++.h>                   
                     using                               namespace                               std;                   
                             
                     const                               int                               MAX = 1000;                   
                             
                     // Constructs a segment tree and stores sTree[]                   
                     void                               buildTree(                               int                               idx,                               int                               ss,                               int                               se, vector<                               int                               > a[],                   
                                         vector<                               int                               > sTree[])                   
                     {                   
                                         /*leaf node*/                   
                                         if                               (ss == se)                   
                                         {                   
                                         sTree[idx] = a[ss];                   
                                         return                               ;                   
                                         }                   
                             
                                         int                               mid = (ss+se)/2;                   
                             
                                         /* building left subtree */                   
                                         buildTree(2*idx+1, ss, mid, a, sTree);                   
                             
                                         /* building right subtree */                   
                                         buildTree(2*idx+2, mid+1, se, a, sTree);                   
                             
                                         /* merging left and right child in sorted order */                   
                                         merge(sTree[2*idx+1].begin(), sTree[2*idx+1].end(),                   
                                         sTree[2*idx+2].begin(), sTree[2*idx+2].end(),                   
                                         back_inserter(sTree[idx]));                   
                     }                   
                             
                     // Recursive function to count smaller elements from row                   
                     // a[ss] to a[se] and value smaller than or equal to k.                   
                     int                               queryRec(                               int                               node,                               int                               start,                               int                               end,                               int                               ss,                               int                               se,                   
                                         int                               k, vector<                               int                               > a[], vector<                               int                               > sTree[])                   
                     {                   
                                         /* If out of range return 0 */                   
                                         if                               (ss > end || start > se)                   
                                         return                               0;                   
                             
                                         /* if inside the range return count */                   
                                         if                               (ss <= start && se >= end)                   
                                         {                   
                                         /* binary search over the sorted vector                   
                                         to return count >= X */                   
                                         return                               upper_bound(sTree[node].begin(),                   
                                         sTree[node].end(), k) -                   
                                         sTree[node].begin();                   
                                         }                   
                             
                                         int                               mid = (start+end)/2;                   
                             
                                         /*searching in left subtree*/                   
                                         int                               p1 = queryRec(2*node+1, start, mid, ss, se, k, a, sTree);                   
                             
                                         /*searching in right subtree*/                   
                                         int                               p2 = queryRec(2*node+2, mid+1, end, ss, se, k, a, sTree);                   
                             
                                         /*adding both the result*/                   
                                         return                               p1 + p2;                   
                     }                   
                             
                     // A wrapper over query().                   
                     int                               query(                               int                               start,                               int                               end,                               int                               k, vector<                               int                               > a[],                               int                               n,                   
                                         vector<                               int                               > sTree[])                   
                     {                   
                                         return                               queryRec(0, 0, n-1, start, end, k, a, sTree);                   
                     }                   
                             
                     // Driver code                   
                     int                               main()                   
                     {                   
                                         int                               n = 3;                   
                                         int                               arr[][3] = { {2, 4, 5},                   
                                         {3, 4, 9},                   
                                         {6, 8, 10}};                   
                             
                                         // build an array of vectos from above input                   
                                         vector<                               int                               > a[n];                   
                                         for                               (                               int                               i=0; i<n; i++)                   
                                         for                               (                               int                               j=0; j<n; j++)                   
                                         a[i].push_back(arr[i][j]);                   
                             
                                         // Construct segment tree                   
                                         vector<                               int                               > sTree[MAX];                   
                                         buildTree(0, 0, n-1, a, sTree);                   
                             
                                         /* un-comment to print merge sort tree*/                   
                                         /*for (int i=0;i<2*n-1;i++)                   
                                         {                   
                                         cout << i << "  ";                   
                                         for (int j=0;j<sTree[i].size();j++)                   
                                         cout << sTree[i][j]<<" ";                   
                                         cout << endl;                   
                                         }*/                   
                             
                                         //  Answer queries                   
                                         cout << query(0, 1, 5, a, n, sTree) << endl;                   
                                         cout << query(1, 2, 1, a, n, sTree) << endl;                   
                                         cout << query(0, 2, 6, a, n, sTree) << endl;                   
                             
                                         return                               0;                   
                     }                   

输出：

5
0
6

buildTree（）分析： 构建合并排序树需要O（N logn）时间，这与合并排序算法相同。它还需要O（n logn）额外的空间。 查询（）分析： 从“开始”到“结束”的范围最多可分为日志（n）部分，我们将对每个部分执行二进制搜索。二进制搜索需要O（logn）。因此总复杂度O（logn*logn）。

本文由 维尼特贾哈酒店 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章