K-D Tree
A k-D tree (KDT, short for k-dimensional tree) is a data structure that handles information in \(k\)-dimensional space efficiently.
It is time-efficient when the number of nodes \(n\) is much larger than \(2^k\).
In competitive programming problems, usually \(k=2\). The complexity analysis on this page treats \(k\) as a constant.
Building the tree
A k-D tree has the shape of a binary search tree, and each of its nodes corresponds to a point in \(k\)-dimensional space. The points of each subtree all lie inside a \(k\)-dimensional hyperrectangle, and every point inside that hyperrectangle belongs to the subtree.
Suppose we know the coordinates of \(n\) distinct points in \(k\)-dimensional space. To build a k-D tree from them, proceed as follows:
-
If the current hyperrectangle contains only one point, return that point.
-
Choose a dimension, and split the current hyperrectangle into two along it.
-
Choose the split point: pick a point along the chosen dimension. The points whose value in this dimension is smaller than that of the chosen point go into one hyperrectangle (the left subtree), and the rest go into the other (the right subtree).
-
Make the chosen point the root of this subtree, recursively build the left and right subtrees from the two hyperrectangles, and maintain the subtree information.
Here is an example with \(k=2\) to make this concrete.
The k-D tree built from it might look like this:
The coordinates at each node of the tree are those of the chosen split point, and the \(x\) or \(y\) next to a non-leaf node is the chosen splitting dimension.
Built this way, the tree has no guaranteed complexity. Two optimizations to steps \(2\) and \(3\) fix this:
- Cycle through the \(k\) dimensions, so that every dimension is split within any \(k\) consecutive levels.
- Whenever you choose a split point along a dimension, choose the median in that dimension. This makes the left and right subtrees as close in size as possible.
With optimization \(2\), the height of the resulting k-D tree is at most \(\log n+O(1)\).
The bottleneck in building a k-D tree is now to select the median in one dimension quickly, and to place the points whose value in that dimension is smaller than the median to its left and the rest to its right. Sorting along the dimension with sort every time gives \(O(n\log^2 n)\). In fact, finding the median of \(n\) elements and putting it in its correct sorted position can be done in \(O(n)\) per call.
Recall how quicksort works. Each time, we pick a number and move the numbers smaller than it to its left and the larger ones to its right, which puts it in its correct sorted position; then we recursively sort the values on the left and on the right. The expected complexity is \(O(n\log n)\). A k-D tree, however, only needs the median to be in its correct sorted position, so we recurse only into the one side that contains the median. It can be shown that this takes \(O(n)\) expected time. The algorithm library has a function that does exactly this, nth_element(). To find the value that would be at position s[mid] if the values between s[l] and s[r] were sorted by the ordering cmp, with the values to the left of s[mid] smaller than s[mid] and those to the right larger, just write nth_element(s+l,s+mid,s+r+1,cmp).
With this idea, a k-D tree can be built in \(O(n\log n)\) time.
Operations in high-dimensional space
To query some information about all the points inside a high-dimensional rectangular region, store at each node the maximum and minimum coordinate in every dimension over its subtree. If the rectangle of the current subtree does not intersect the query rectangle, do not search the subtree any further. If it is completely contained in the query rectangle, return the sum of the weights of all points in the subtree. Otherwise, check whether the current point lies in the query rectangle, update the answer, and recurse into the left and right subtrees.
Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 | |
Complexity analysis
Consider two dimensions first. For a query rectangle \(R\), we divide the nodes of the k-D tree into three classes:
- Disjoint from \(R\).
- Completely contained in \(R\).
- Partially contained in \(R\).
Clearly the cost of a single query is the number of class 3 nodes. The rectangle of a class 3 node either completely contains \(R\), or neither of the two contains the other. There are clearly only \(O(h)=O(\log n)\) nodes of the first kind, so we now count those of the second kind.
First, we may shift every side of the rectangle by \(\epsilon\) so that the query rectangle does not pass through any existing point. This clearly does not change the set of points the query covers.
For a class 3 node of the second kind, some side of \(R\) must pass through its rectangle. So it suffices to count the rectangles that each side of \(R\) passes through, that is, the largest number of node rectangles that any one segment can cross.
Take a node \(u\). It has four grandchildren, and on the way down to each of them one split is made in each of the two dimensions. When a rectangle is partitioned into four subrectangles in this way, a segment parallel to a coordinate axis crosses at most two of the regions. In other words, a query starting from \(u\) still finds class 3 nodes in at most two of the grandchildren it descends into. (This may fail if the segment coincides exactly with a splitting boundary, but shifting the sides of the query rectangle has ruled that case out.)
Because every node, at build time, is the median of its whole subtree in the current splitting dimension, the subtree size is halved at each level. So, letting \(n\) be the size of the subtree of \(u\), we can write the following recurrence:
By the master theorem, \(T(n)=O(\sqrt{n})\).
For a fixed number of dimensions \(k\ge 2\) the recurrence becomes \(T(n)=2^{k-1}T(n/2^k)+O(1)\), so \(T(n)=O(n^{1-\frac1k})\). For \(k=1\) the recurrence is \(T(n)=T(n/2)+O(1)\) and the complexity is \(O(\log n)\).
Insertion and deletion
If the \(k\)-dimensional point set being maintained can change, that is, points may be inserted or deleted, the k-D tree is no longer guaranteed to stay balanced. Because of the way a k-D tree is constructed, the rotations of a binary search tree cannot be used directly to keep it balanced, and random priorities like those of an FHQ treap do not guarantee its complexity either. Several ways of maintaining the tree are described below. All of them assume that \(k\ge 2\) is a constant and that a query asks for the count or the sum of the weights inside a rectangle.
Scapegoat-style rebuilding
Consider the case with insertions only. After an insertion, check the subtree sizes along the insertion path, flatten any unbalanced subtree, and build it again by medians. The rebuild still chooses the splitting dimension cyclically, according to the depth of the node. Fix a constant \(\frac12<\alpha<1\) and require that after every operation each node satisfies
Under this weight-balance condition, the worst-case time complexity of a single query is guaranteed to be
Here \(n\) is the number of nodes kept in the tree. For a fixed \(\frac12<\alpha<1\) we have \(1-\frac1k<p<1\). For example, \(p\approx 0.5757\) for \(k=2\), \(\alpha=0.6\), and \(p\approx 0.7067\) for \(k=2\), \(\alpha=0.75\).
Proof of complexity
Consider the hyperplane \(x_i=c\) that contains one of the boundaries, and count only the non-empty subtrees whose bounding box is crossed by this hyperplane.
At a split along the \(i\)-th dimension, the bounding box of at most one child is crossed, and that child is at most \(\alpha\) times as large as its parent. At a split along any other dimension, the bounding boxes of at most two children are crossed, but their sizes add up to at most the size of the parent. Hence, every time we go down \(k\) full levels, the number of crossed subtrees grows by a factor of at most \(b=2^{k-1}\), while the total size of these subtrees shrinks by a factor of at least \(\alpha\).
Let \(a_j\) be the number of crossed non-empty subtrees at depth \(jk\). Bounding it once by the count and once by the total size gives
and between two consecutive depths of this form there are only \(k-1\) levels, which contribute at most a constant factor more nodes, so the total is
Let \(L=\lfloor\log_{b/\alpha}n\rfloor\) and split the sum at \(L\), bounding the first part by \(b^j\) and the second by \(n\alpha^j\). This gives
Every node at which the recursion has to continue has a bounding box that is crossed by one of the boundary hyperplanes of the query rectangle, and each such node visits at most two more children. Adding up the contributions of the \(2k\) boundaries gives the upper bound for a single query.
Rebuilding a subtree of size \(s\) takes \(O(s\log s)\) time. Right after a rebuild, both children have size at most \(s/2\), so at least \(\Omega(s)\) points must be inserted into this subtree before the fixed \(\alpha\) weight balance is violated again. Charge the cost of the rebuild to these insertions: each insertion pays \(O(\log N)\) at each of its ancestors, and it has \(O(\log N)\) ancestors, so the amortized complexity of one insertion is \(O(\log^2 N)\), where \(N\) is the maximum size of the tree over the course of the operations.
Square root rebuilding
To insert, first store the new point; rebuild once every \(B\) insertions.
To delete, just mark the point as deleted. If the requirements are stricter, keep track of how many points in the tree have been deleted and rebuild when the count reaches \(B\).
An update takes amortized \(O(n\log n/B)\) time and a query takes \(O(B+n^{1-\frac1k})\). If the numbers of updates and queries are of the same order of magnitude, \(B=O(\sqrt{n\log n})\) is optimal (an update then takes \(O(\sqrt{n\log n})\) and a query \(O(\sqrt{n\log n}+n^{1-\frac1k})\)).
Binary grouping
Maintain several k-D trees whose sizes are natural-number powers of \(2\) and add up to \(n\).
To insert, add a new k-D tree of size \(1\), then keep merging trees of equal size (flatten them and rebuild directly). An implementation can get by with a single rebuild.
The trees that have to be merged always have sizes that start at \(2^0\) and have consecutive exponents. Over \(n\) insertions starting from an empty structure, a tree of size \(2^i\) is rebuilt at most \(O(n/2^i)\) times, at a cost of \(O(2^i(i+1))\) each time. Summing over all \(i\), the total time is \(O(n\log^2 n)\), so the amortized complexity of one insertion is \(O(\log^2 n)\).
To query, simply query each tree separately, which takes \(O\left(\sum_{i\geq0} (\frac n{2^i})^{1-\frac1k}\right)=O(n^{1-\frac1k})\).
So, for a sequence of operations that consists only of insertions and rectangle count or sum queries, binary grouping keeps the amortized insertion complexity at \(O(\log^2 n)\) and the space at \(O(n)\), and still achieves a better query bound than the weight-balance analysis above gives for a fixed \(\alpha>\frac12\).
Example
Luogu P4148 Simple Problem
A 2D matrix of size \(n\times n\) initially contains only \(0\). Perform \(q\) operations on it, each of one of the following two kinds:
1 x y A: add \(A\) to the number at coordinates \((x,y)\).2 x1 y1 x2 y2: print the sum of the numbers inside the rectangle with lower-left corner \((x1,y1)\) and upper-right corner \((x2,y2)\) (including its boundary).
The queries are forced online. The memory limit is 20M. The answers and all intermediate values are guaranteed to fit in an int.
\(1\le n\le 500000 , 1\le q\le 200000\)
The 20M memory limit rules out every nested-tree solution, and forced online rules out CDQ divide and conquer, so a k-D tree is the only option.
The reference code below uses binary grouping.
Reference 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 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 | |
Neighborhood queries
Warning
Finding the nearest point with a k-D tree still takes \(O(n)\) per query in the worst case, though it remains an excellent way of fishing for partial points; keep this in mind when you use it. Neighborhood queries are explained here only to deepen your understanding of the structure of a k-D tree.
Example: Luogu P1429 Closest Pair of Points in the Plane (Harder Version)
Given \(n\) points \((x_i,y_i)\) in the plane, find the Euclidean distance between the two closest points.
\(2\le n\le 200000 , 0\le x_i,y_i\le 10^9\)
First build a 2-D tree on these \(n\) points.
Iterate over the nodes, and for each one find the nearest point other than the node itself; this yields the answer. Traversing every node of the 2-D tree by brute force costs \(O(n)\) each time, so pruning is needed. For each subtree, maintain the minimum and maximum coordinate of its nodes in every dimension. Suppose the closest pair of points found so far is at distance \(ans\). If the smallest distance from the query point to the rectangle that contains all the points of a subtree is greater than or equal to \(ans\), the subtree cannot contain the answer, and the search does not enter it.
A heuristic search helps as well: if both subtrees of a node may contain the answer, search first in the one that is closer to the query point. In effect, the smallest distance from the query point to the rectangle of a subtree is the heuristic function for this problem.
Reference 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 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 | |
Example: [CQOI2016] K-th Farthest Pair of Points
Given \(n\) points \((x_i,y_i)\) in the plane, find the distance between the points of the \(k\)-th farthest unordered pair under Euclidean distance.
\(n\le 100000 , 1\le k\le 100 , 0\le x_i,y_i<2^{31}\)
This is similar to the previous example. The closest pair of points becomes the \(k\)-th farthest pair, and the heuristic function becomes the largest distance from the query point to the rectangular region of a subtree. Use a min-heap to maintain the distances of the \(k\) farthest pairs found so far: if the distance of the pair just found is greater than the top of the heap, pop the top and insert this distance. As before, prune with the distance at the top of the heap.
The problem asks about unordered pairs, that is, swapping the two points gives the same pair. Each unordered pair is therefore counted twice, so the \(k\) read from the input must be multiplied by \(2\).
Reference 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 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 | |
Practice problems
[Violet] Angel Doll / SJY Places Pieces
[Chinese national training team] JZPFAR
[CH Weak Provinces Mutual Test R2] TATT
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: hsfzLZH1, Ir1d, JosephusW, Xeonacid, 24OI-bot, ouuan, Rainboylvx, Henry-ZHR, Chrogeek, Enter-tainer, kenlig, ksyx, StudyingFather, minamimelon, CCXXXI, shuzhouliu, Eletary, xizai-cmd, Tiphereth-A, c-forrest (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.