Today see the concept of a little chairman tree, plus fly elder brother last time speak, at present have a general understanding of chairman tree, talk about it simply, do not speak code, only speak ideas, post in the future!
Orz Advanced Data Structure Inventor Chairman!! I first saw this word in the courseware of CLJ for the first time. Recently, I thought of this word when I made the interval KTH large. There is very little information in this respect, so I worship the chairman again.
After all, according to the inventor: “The idea is to build a line tree for each prefix [1.. I] of the original sequence to maintain the number of occurrences of each number in the range, and then find that such a tree can be subtracted, and then nothing.”
The chairman tree can be used to solve the following problem: “Give a list of numbers, A1, A2… An, what is the KTH largest number between ai and AJ?”
Building that many line segment trees is obviously MLE!! But just to make it easier to understand, let me put this down. Let’s open a new array t[n] that holds the sorted and de-duplicated values of an.
So what does each line segment tree maintain? It’s the number of occurrences in t[n] between A1 and AI. An: 4, 1, 2, 8, 9, 4, 4, 3
Sort and de-duplicate to get {tn}
Tn: 1, 2, 3, 4, 8, 9
The following is the prefix a[1..9] construction tree, which has two 1’s, one 2, one 3, three 4’s, one 8’s and one 9’s, so its occurrence frequency is the value maintained by the segment tree (denoted as Cn for clear representation). After the construction of the tree, the value of each node in the tree represents the occurrence frequency of the digit in T [I,j] in A [1..9] and, I, J is the interval marked below the node.
So let’s figure out how to find the KTH largest value for this tree. For example, what is the sixth largest number in A [1..9]? We see that the left son of the root node has only 4 elements, so the sixth largest number must be in the right son, and we can recurse the problem to find the second largest number in the interval t[1],t[2] and t[3] after all the numbers are removed as a[1],t[2] and t[3]. (c[1]+ C [2]+c[3]=4, then 6-4=2). We see that the left son (interval t[4,5]) at this time has 4 elements, 4>2, so the second largest number must be in the left son, recursively into the left son, at this time, the two numbers in the interval T [4,5]
What is the second largest number for a[1..9] after all numbers are removed into t[1],t[2],t[3],t[6]. Finally, the interval [4,4] has three elements, 3>2, so the second largest number must be in the interval [4,4], namely T [4]=4, so the sixth largest number in a[1..9] is 4.
For every I, a[1, I] has a tree, finding the KTH greatest of a[L,R] is similar to finding the KTH greatest of a[1,R], as long as we subtract the corresponding part of the tree where A [1, L-1] is located at each level of recursion. For example, in a[L,R], there are 6 numbers less than t[mid]. There are 2 numbers a[1,L-1] less than t[mid], then there are 6-2=4 numbers a[L,R] less than t[mid], the recursive process is similar to the above, no further elaboration.
Let’s deal with the MLE meme. As is drawn below, A1… Trees with a prefix of 5 to 9 and then find that the trees are all very similar!!
This is the space that we can compress. For example, the right subtree of a tree prefixed with a[1..9] is the same as the right subtree of a tree prefixed with a[1..8]!! Therefore, when building tree A [1..9] (from 1 to 9), the root node can directly connect an edge to the right subtree of A [1..8]. Similarly, for the left son of the root node (now consider this point as the root node), its left subtree is the same as the corresponding part of a[1..8], and therefore has an edge, as shown in the figure below
This way we only add 3 points but save all the information for both trees!! To build a tree like this, all we need to do is open an array to store the position of the root indicated by the two arrows in the diagram, and walk down the root to create a complete line segment tree as described earlier