preamble
\(\text{K-D Tree (K-Dimension Tree)}\) It is a data structure that can efficiently handle high-dimensional information.
In general informatics competition topics\(k = 2\)At this point it is also known as\(\text{2-D Tree}\)。
But unfortunately.\(k \ge 3\) of the situation is not common, and this we will explain why later.
Algorithm Description
concern
Consider first the simple case, assuming that the information is only one-dimensional, then we usually maintain it in a line tree, so that for any interval\([l, r]\), which we can express as the sum of several subintervals.
But now the message becomes\(k\) dimension, a direct line segment tree is definitely not possible. So we consider a line tree-like, for the\(k\) The dimensional space is partitioned by representing any hypercube as a disjoint union of several subspaces of the partitioned space.
However, the above problem is too difficult to have any effective solution. So consider a weaker version:
- state in advance\(k\) in dimensional space\(n\) points, one hypercube at a time is given, and the set of points that will be contained by this hypercube is represented by a smaller number of nodes.
That's\(\text{K-D Tree}\) Abstraction problems that need to be solved.here areis a boilerplate question, and it may be that the questions in the questionnaire are not correct for the\(\text{K-D Tree}\) The nature of the portrayal is not comprehensive, resulting in some strange mo team can pass, but this important, people take the test!\(\text{K-D Tree}\) Just fine.
Some people may ask: is not just a few more dimensions, write a tree set on the tree is not\(\text{poly}(\log n)\) Of what?
But obviously not all high-dimensional problems tree-set trees are applicable.The essence of tree-set trees is to separate the two dimensions, not the\(\text{K-D Tree}\) Total solution used, such a structure would have the following drawbacks:
-
Modifications cannot be supported. Because your first level tree (assuming it's a line segment tree) will split the original information into\(O(\log n)\) copies, you can only locate one of them each time you modify it in the first tree, so tree nesting is not supported when you modify it.
-
Cannot handle some special problems. For example, the structure of a line tree supports line tree bisection, line tree partitioning, even one-sided recursion, and so on. These are obviously not supported on a 2D line tree, and the\(\text{K-D Tree}\) It's supportive.
Pre-discussion: Leafy or Nodey?
We know that tree structures are very graceful, and many data structures are essentially a tree (even sequence chunking can be seen as such).
However, these data structures do not maintain information in exactly the same way: for example, a line tree has only the leaf nodes storing the original information, and the other nodes storing the merge of the information of a number of leaf nodes; unlike a balanced tree, where each node merges the information of all of its descendants as well as adding its own information.
For a line tree likeData structures that store the original information at the leaves onlyWe call it the\(\text{Leafy}\) The.
And for balanced trees likeA data structure that stores a copy of the original message at each nodeWe call it the\(\text{Nodey}\) The.
common\(\text{Leafy}\) The data structure is the line tree, and various variants of the line tree. And then there's the\(\text{WBLT}\) cap (a poem)\(\text{Leafy Tree}\) also\(\text{Leafy}\) I've never even written about it, so it's good to mention it here.
(indicates contrast)\(\text{Nodey}\) structures are generally found more often in balanced trees.\(\text{OI}\) the most common\(\text{Treap}\) cap (a poem)\(\text{Splay}\) just like\(\text{Nodey}\) The reason for this is well understood: balanced trees have to support dynamic insertion and deletion. The reason is well understood: balanced trees have to support dynamic insertion deletion, the\(\text{Leafy}\) The structure is not good to maintain it.
Here's the problem.\(\text{K-D Tree}\) be\(\text{Leafy}\) still\(\text{Nodey}\) What about it?
Actually, it's both, and both have been written about. Personally, I tend to think it would be better to put\(\text{K-D Tree}\) put down as\(\text{Leafy}\) The reason why it's better:
-
evidently\(\text{Leafy}\) (particle used for comparison and "-er than")\(\text{Nodey}\) It's better to write because\(\text{Leafy}\) is a dichotomous structure, whereas\(\text{Nodey}\) Equivalent to a three-part structure. It is also generally\(\text{Leafy}\) The data structure constants are smaller.
-
We'll get to that later.\(\text{K-D Tree}\) Partition, which must be used to\(\text{Leafy}\) Structure. It's not hard to find\(\text{Nodey}\) structure is naturally impossible (or difficult, since you can of course add a leaf below each node to force it into a\(\text{Leafy}\) structure, and then line segment tree partitioning, so why bother?) In favor of line tree partitioning.
-
\(\text{K-D Tree}\) A lot of what is maintained are offline questions, and very few (not that there aren't any, they're rare) require dynamic insertion and deletion that also comes with forced online. If you see something like the above, please reflect on whether the question is any better, or doesn't need to be\(\text{K-D Tree}\) practices.
So we gave it up.\(\text{Nodey}\) structure brings with it the advantage of easy insertion deletion, and instead chose to incorporate the\(\text{K-D Tree}\) add sth. into a group\(\text{Leafy}\) Structure.
Of course you have to learn\(\text{Nodey}\) The version is also possible to go next door to the\(\text{OI-Wiki}\) Take a look. But even if your\(\text{K-D Tree}\) always have been\(\text{Nodey}\) of I'm afraid it doesn't have much effect on what follows.
algorithmic process
make a contribution
Now consider giving\(k\) in dimensional space\(n\) A point on how to build a tree.
Since we want to quickly localize a hypercube, we still divide it into front and back halves similar to a line tree for sorting a dimension.
In the line tree we don't have to think about which dimension to choose because there is only one. But now expanding to\(k\) Vi, we have to make a choice.
It's easy to think of us alternating divisions, such as\(k = 2\) situation, we are for the first time interested in the first\(1\) The dimensions are divided, with the first\(2\) objection\(2\) The dimensions are divided, with the first\(3\) The next time you go back to the first\(1\) dimensions, and so on.
For example, the following figure is\(k = 2\) The situation:
We keep dividing until there is only one point in the point set, at which point it means we have gone to a leaf node and can return directly.
One implementation detail is that we are equivalent to looking for the top of a certain dimension in the\(k\) small values, this can be done using the\(\text{nth_element}\) function with linear time complexity.
Finally for each non-leaf node, remember to maintain the point set\(k\) The maximum and minimum coordinates of each dimension in the dimension, which will be needed later to speed up the query. This can be merged up directly from the two sons.
Unlike a general line tree, the\(\text{K-D Tree}\) The time complexity of tree building is\(O(n \log n)\), because the topic is given a point set, and you need to do a sort-like operation on this point set, so the band\(\log\) It is unavoidable.
As we will see later, however, the complexity of building trees is negligibly small compared to queries and other operations.
consult (a document etc)
Consider that we want to query a hypercube and we are currently in the\(\text{K-D Tree}\) up a node\(p\)。
We realized there was no good way to do this at this point, and the only thing we could do was two things:
- If the query hypercube contains\(p\) represents all the points in the point set, then the localization is successful and returns directly to the\(p\)(or\(p\) (some of the information maintained at) will suffice.
- If the query hypercube is the same as\(p\) represents the largest hypercube enclosing the set of points away from each other, the\(p\) All points in the point set cannot be in the query hypercube, and all we directly\(\text{return}\)。
Both of the above steps can be done by using each dimension within the subtree we maintained earlier\(\min/\max\) Rapid processing.
If neither of the above cases is satisfied, then there is nothing we can do to recursively recurse both subtrees (obviously if they are leaves they must fall into one of the two previous cases).
Later we will demonstrate that doing sointerviewscap (a poem)localizationThe number of nodes of\(O(n^{1 - \frac{1}{k}})\) The. Here we clarify a few concepts:
- interviewsrefers to the total number of nodes passed through during the query. WhilelocalizationRefers to nodes that split the set of points in a hypercube into nodes that satisfy that these nodes do not intersect two by two and are concatenated is something you query.
So the time complexity is\(O(n^{1 - \frac{1}{k}})\)regard as\(k = 2\) When we do, we'll get\(O(\sqrt n)\)。
complexity analysis
Recall how we proved the time complexity of a line tree. We found that if the query is a prefix or a suffix, then we only need one-sided recursion, and the time complexity\(O(\log n)\)。
And how can arbitrary intervals be analyzed? Consider that if the query does not contain a midpoint, it will be recursive only one way. If it contains a midpoint, the original interval becomes two prefixes or suffixes. So the time complexity is also\(O(\log n)\) The.
Consider analyzing in a similar way\(\text{K-D Tree}\) of time complexity. Consider first the\(k = 2\) case, we find that the query of an arbitrary rectangle has no properties, so we try to turn it into a rectangle with properties like prefixes/suffixes.
For any rectangle, which does not have any dimension that is a prefix/suffix, we call the\(\text{4-side}\) rectangle, consider an analysis similar to the previous line tree, splitting it into\(O(1)\) classifier for individual things or people, general, catch-all classifier\(\text{2-side}\) Rectangle.
Next we only analyze the\(\text{2-side}\) The query for a rectangle (assuming it is a lower-right rectangle), set the\(T(n)\) pray for the sake of\(n\) of a node\(\text{K-D Tree}\) The time complexity of the upper query. Consider the worst-case scenarios shaped like the following two:
Consider the first case, where the lower right rectangle is contained and the upper left rectangle is disjoint, and the time complexity of processing them is\(O(1)\)And the remaining two pieces are still\(\text{2-side}\)follow
By the Master's Theorem\(T(n) = O(\sqrt n)\)。
In the second case, the lower right rectangle is completely contained and the upper left rectangle is\(\text{2-side}\), while the remaining two note that it is\(\text{1-side}\)(This may not be rigorous, but I won't change it for ease of understanding.) We set up the processing\(\text{1-side}\) The query time complexity is\(T_0(n)\)。
imitate
consider and analyze\(T_0\), it is clear that after one horizontal and one vertical split each, there are at most two remaining\(\text{1-side}\) rectangle, whereupon
commander-in-chief (military)\(T_0\) Take it back and get
This recursive formula draws a recursive tree by hand and finds that it also satisfies\(T(n) = O(\sqrt n)\) The.
In this way we have proved that\(k = 2\) hour\(\text{K-D Tree}\) The time complexity is\(O(\sqrt n)\)。
insofar as\(k \ge 3\) case, and since it is rarely used, the proof is omitted, concluding that\(T(n) = 2^{k - 1}T(\frac{n}{2^k}) + O(1) = O(n^{1 - \frac{1}{k}})\)。
For proof, I think it works with the method above. Let's start by replacing the\(\text{2k-side}\) Rectangularize to\(\text{k-side}\) rectangle, and then analyzing it will reveal that it is sufficient to halve the size after one round of division for all dimensions.
for what reason?\(k \ge 3\) infrequently used
After analyzing the complexity, it is easy to understand why the\(\text{3/4-D Tree}\) Even higher dimensions are not commonly used anymore.
Going back to the previous complexity analysis, we find that by combining the\(\text{2k-side}\) The rectangle becomes\(\text{k-side}\) When rectangles are used, each time the problem size will\(\times 2\)。
so to speak\(\text{K-D Tree}\) Implicitly, a\(2^k\) The constants (and possibly a\(k\) (the constant of which is doubtful). Although\(k = 2\) It is largely negligible at times, but with\(k\) increases, this constant grows exponentially.
add on\(\text{K-D Tree}\) The intrinsic complexity is\(O(n^{1 - \frac{1}{k}})\)in\(k\) Larger by itself with\(O(n)\) The difference as well is not that big, plus it's a big constant, and you can understand why sometimes you write a\(\text{5-D Tree}\) And then couldn't run away from the violence.
And then, of course, there's the fact that the\(\text{OI}\) Topics above the middle third dimension are inherently uncommon, and the most commonly seen are axes and planes, which makes the\(\text{K-D Tree}\) Much less useful.
When it comes to real 3-D problems, there's usually\(\text{polylog}\) practices (e.g., tree over tree.\(\text{CDQ}\) partitioning), and at the very least, some method (which may cost a\(\log\)) Get rid of one dimension and get back on\(\text{2-D Tree}\)This gives us\(O(\sqrt n \log n)\) maybe\(O(\sqrt n)\)（\(\text{K-D Tree}\) Some of the features may be able to incorporate\(\log\) (spread evenly off) the practice.
I've seen people talk about it before.\(\text{K-D Tree}\) When written directly as\(\text{2-D Tree}\) The. While this may not be conducive to understanding this data structure, it's not all bad - because the\(k \ge 3\) The usage scenarios are indeed too small.
If I were asked to summarize:
- If your algorithm requires\(\text{3-D Tree}\), make sure you think carefully about whether to use it, double-check your algorithm, and make it clear that its time complexity is\(O(n^{\frac{2}{3}})\)and also in calculating the time complexity with the\(10\) The constants of the
- If your algorithm requires\(\text{4D}\) upper\(\text{K-D Tree}\), please abandon your current train of thought immediately and rethink the question.
Dynamic expansion
insertion
Noting the establishment of\(\text{k-D Tree}\) The time complexity of\(O(n \log n)\)and the time complexity of the query is\(O(\sqrt n)\), which is a structure well suited to the root partition.
set a threshold\(B\), when the inserted point\(< B\) Instead of inserting them, they are stored uniformly, and the query counts the contribution of these points to it, and when the number of inserted points reaches\(B\) When reconfiguring the entire\(\text{K-D Tree}\)。
Depending on the implementation, the time complexity is\(O(n \sqrt{n \log n})\) maybe\(O(n \sqrt n)\)。
There seems to be a binary grouping approach with about the same complexity, but I think the\(\text{K-D Tree}\) More compatible with root partitioning, binary grouping in general is used in conjunction with data structures such as line trees, which can amortize an\(\log\), and can also do line segment tree merging. So this method will not be expanded.
with deletion
There's not much you can do about this, or you can only consider inert deleting it, marking it for deletion, and refactoring it periodically if the topic restrictions are loose. Or consider going offline.
If the topic is so restrictive that the options above are unacceptable, then consider writing\(\text{Nodey K-D Tree}\) Right.
example
From ix35：
Given a two-dimensional plane of\(n\) points, supports two operations\(q\) Times:
- Weights all the points in a rectangular area by\(+v\)。
- Find the minimum value of the weights of the points in a rectangular region.
expense or outlay\(\text{K-D Tree}\) maintenance, each rectangle is localized to the tree\(O(\sqrt n)\) points, the operations on the nodes are similar to a line tree.
time complexity\(O(n \log n + q\sqrt n)\)。
Function Expansion
As we all know.\(\text{K-D Tree}\) There is also a use for finding the nearest/farthest point pairs of a plane.
The approach is to enumerate a point\(i\)in\(\text{K-D Tree}\) Query the nearest/farthest point on the\(\text{K-D Tree}\) structure can be used for pruning. For the\(\text{K-D Tree}\) A bounding rectangle is computed for each node on the Then the distance within the rectangle\(i\) The closest/farthest point must be one of the four vertices of the rectangle, if all four vertices are not as close as the current\(ans\), then there is no need to search within that subtree.
\(k\) Near /\(k\) Farpoint pairs do something similar, using the heap to maintain the current ex\(k\) Excellent answer, or just use pruning in a similar way as before.
This performs excellently with random data. But it's still essentially violent pruning, and the worst time complexity is still\(O(n^2)\) The.
Two-dimensional contribution issues /\(\text{2-D Tree}\) partition
This is something I first saw at JOI Open 2018 Collapse.
think overThe following issues：
there are\(n\) A graph, each of which is located at a position in the two-dimensional plane\((x, y)\)，\(q\) operations, each time connecting an edge in a graph within a rectangle. Find the final number of connected blocks per graph.
Consider that for a single edge-adding operation, locating the\(\text{K-D Tree}\) upper\(O(\sqrt n)\) Nodes. Just run something like a line tree partition at the end.
The time complexity is\(O(q \sqrt n \log n)\)。
Comparison with other algorithms
In the case of the Collapse question, there is actually another way to do it. Here's a quoteMy solution to the problem：
First redescribe the question: each side\((u, v)\) Appearance time\([l, r]\)Every time you ask at the time\(t\)If you only keep the\([1, x]\) cap (a poem)\([x + 1, n]\) The interior edges, how many connected blocks.
evidently\([1, x]\) cap (a poem)\([x + 1, n]\) The two parts can be calculated separately for the number of connected blocks and then summed, and the two parts are pairwise, so we consider below only the calculation of the\([1, x]\)。
We respond to all inquiries by\(t\) Sorting, and then sorting each\(B\) The queries are grouped into chunks, and consider how the answer is counted for each chunk.
Examining the contribution of each edge to these inquiries, let the time of appearance of this edge be\([l, r]\)The time period for inquiries within the block is\([L, R]\)。
as\([l, r]\) embody\([L, R]\), then this edge contributes to the whole block, and we press all such edges by\(y\) The queries within a block are sorted by\(x\) Sorting, scanning the line is sufficient. Time Complexity\(O(\frac{qm}{B} \log n)\)。
as\([l, r]\) Not included but related to\([L, R]\), then for each edge it will only fall into this case\(O(1)\) times, at this point we violently join edges of this type when we encounter a query, and then just undo back in, and the parallel check set needs to be merged by rank. Time Complexity\(O(mB \log n)\)。
total time complexity\(O((\frac{qm}{B} + mB) \log n)\)The code takes\(B = 333\)(randomly taken, not carefully carded). Since the concatenated set and the sorted\(\log\) The constants are very small and the way this question is added to the edge is hard to jam full and passable.
Consider applying this practice to that previous question:
We're still interested in all points pressing\(x\) Sorting and then chunking, a rectangle if it is in the\(x\) dimension covers all the points within the current block, then the value of its\(y\) Dimensional scan lines, otherwise violence is sufficient.
But the problem arises at this point, the rectangles in Collapse are prefixed in one dimension, so the process of doing the scan line is only adding and not deleting. But this question is an arbitrary rectangle, so we also have to consider the case of deletion. Obviously the parallel check set is not good for deletion, so we also have to do the line tree partition again, then the complexity is\(O(n \sqrt n \log^2 n)\) maybe\(O(n \sqrt{n \log n} \log n)\) s, than the\(\text{K-D Tree}\) partition\(\log\)。
So this chunking practice only applies when the rectangle is\(\text{3-side}\) when the time complexity is\(O(n \sqrt n \log n)\)。
without doubt\(\text{2-D Tree}\) The partitioning approach has its drawbacks, and without any very good implementation, it has a space complexity of\(O(n \sqrt n)\), and then I think it's slightly larger than the chunking constant. But it has the advantage of being very intuitive and very versatile to set templates,