The partition tree is a data structure based on the line segment tree. It also uses the idea of divide and conquer, but it is much more efficient than the line segment tree. Why is this? Because the division tree has another property: it is not divided randomly during division, nor is it divided directly after sorting (because this will destroy the original structure), but the original relative order is maintained after sorting and then divided into left and right subtrees.
Specific implementation methods:
The whole process is divided into two stages: tree building and query:
Figure 1 Partition tree
1）make achievements: First define an array tree[30] [1000]. The first dimension represents the number of layers, and the second dimension represents the value of the i-th number in this layer, which is used to represent this partition tree. Then define the sorted[1000] array to store the sorted original sequence, and then record how many of the first i numbers in each layer have entered the left subtree of the next layer. There is toleft[30] [1000] In the array, it is useless in building a tree, but recording it is useful for searching. Use the divide and conquer idea to allocate the left subtree and the right subtree. Allocate the number not greater than the middle value mid to the left subtree, and allocate the number greater than the middle value to the right subtree. In the tree, but sometimes in order to make the left and right numbers as equal as possible, the numbers equal to the middle value must be allocated to both sides, so the same is defined to store the number of numbers equal to the middle value into the left subtree. After the allocation is completed, the left subtree and the right subtree are recursively allocated. As a recursion, there must be an exit. It will return when the recursion reaches the leaf node, that is, if (l==r) return;
2）Query: According to the previously stored array toleft of the number of left subtrees entering the next layer, you can calculate whether the kth largest number in the interval is the left subtree or the right subtree of the current node, and calculate the left and right boundaries of the corresponding subtree of the next layer, and then recurse the corresponding subtree. Same as above, the recursive exit is also returned when it reaches the leaf node. See notes for details...
Without further ado, here is the code:
#include<iostream>
#include<algorithm>
using namespace std;
int tree[30][1000], sorted[1000], toleft[30][1000], n, m, ans;//The two dimensions of tree and toleft store depth and sequence respectively, and sorted stores the sorted sequence.
void buildtree(int l, int r, int dep)//Build partition tree
{ if (l == r) return;//Return when encountering a leaf node int mid = (l + r) / 2;//two points int same = mid - l + 1;//same ultimately saves the number of elements that are the same as the middle value in order to determine which interval it is divided into for (int i = l; i <= r; i++) if (tree[dep][i] < sorted[mid]) same--; int lpos = l; int rpos = mid + 1;//The left pointer and right pointer are not commonly used pointers and are used to store the number of elements in each interval. for (int i = l; i <= r; i++) { if (tree[dep][i] < sorted[mid])//less than the middle value tree[dep + 1][lpos++] = tree[dep][i];//Assigned to the left subinterval else if (tree[dep][i] == sorted[mid] && same > 0)//Equal to the middle value and the number of the same is greater than 0 { same--; tree[dep + 1][lpos++] = tree[dep][i];//Assigned to the right subinterval } else tree[dep + 1][rpos++] = tree[dep][i];//The rest is allocated to the right subrange toleft[dep][i] = toleft[dep][l - 1] + lpos - l;//The toleft array records how many of the first i numbers in this layer enter the left subrange of the next layer, which is useful for querying } buildtree(l, mid, dep + 1);//Build the left subinterval (left subtree) buildtree(mid + 1, r, dep + 1);//Build the right subinterval (right subtree)
}
int search(int L, int R, int l, int r, int dep, int k)//Query the kth largest number
{ if (l == r) return tree[dep][l];//Query the leaf node that meets the requirements and return the corresponding value int mid = (L + R) / 2;//L, R are large intervals (mainly the boundaries of each left subtree and right subtree) int cnt = toleft[dep][r] - toleft[dep][l - 1];//Find out how many people in the [l,r] interval enter the next left subinterval if (cnt >= k)//The k-th largest number corresponds to the node in the left subtree { int newl = L + toleft[dep][l - 1] - toleft[dep][L - 1];//Find the boundary of the interval where the kth largest number in the next layer is located int newr = newl + cnt - 1; return search(L, mid, newl, newr, dep + 1, k); } else//In the right subtree { int newr = r + toleft[dep][R] - toleft[dep][r];//Find the boundary of the interval where the kth largest number in the next layer is located int newl = newr - (r - l - cnt); return search(mid + 1, R, newl, newr, dep + 1, k - cnt); }
}
int main()
{ cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> tree[0][i]; sorted[i] = tree[0][i]; } sort(sorted + 1, sorted + n + 1); // Sort the sorted array buildtree(1, n, 0);//Build tree int a, b, c; for (int i = 1; i <= m; i++) { cin >> a >> b >> c;//Input query cout << search(1, n, a, b, 0, c) << endl;//Query the kth largest number } return 0;
}