Skip to content

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:

  1. If the current hyperrectangle contains only one point, return that point.

  2. Choose a dimension, and split the current hyperrectangle into two along it.

  3. 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).

  4. 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:

  1. Cycle through the \(k\) dimensions, so that every dimension is split within any \(k\) consecutive levels.
  2. 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
int query(int p) {
  if (!p) return 0;
  bool flag{false};
  for (int k : {0, 1}) flag |= (!(l.x[k] <= t[p].L[k] && t[p].R[k] <= h.x[k]));
  if (!flag) return t[p].sum;
  for (int k : {0, 1})
    if (t[p].R[k] < l.x[k] || h.x[k] < t[p].L[k]) return 0;
  int ans{0};
  flag = false;
  for (int k : {0, 1}) flag |= (!(l.x[k] <= t[p].x[k] && t[p].x[k] <= h.x[k]));
  if (!flag) ans = t[p].v;
  return ans += query(t[p].l) + query(t[p].r);
}

Complexity analysis

Consider two dimensions first. For a query rectangle \(R\), we divide the nodes of the k-D tree into three classes:

  1. Disjoint from \(R\).
  2. Completely contained in \(R\).
  3. 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:

\[ T(n)=2T(n/4)+O(1) \]

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

\[ \max\{\operatorname{size}(\mathrm{left}),\operatorname{size}(\mathrm{right})\}\le\alpha\operatorname{size}(\mathrm{parent}). \]

Under this weight-balance condition, the worst-case time complexity of a single query is guaranteed to be

\[ O(n^p),\qquad p=\frac{k-1}{k-1+\log_2(1/\alpha)}. \]

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

\[ a_j\le b^j,\qquad a_j\le n\alpha^j, \]

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

\[ O\left(\sum_{j\ge 0}\min\{b^j,n\alpha^j\}\right). \]

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

\[ \sum_{j\ge 0}\min\{b^j,n\alpha^j\} \le\sum_{j=0}^{L}b^j+n\sum_{j=L+1}^{\infty}\alpha^j =O(n^{\log_{b/\alpha}b})=O(n^p). \]

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. 1 x y A: add \(A\) to the number at coordinates \((x,y)\).
  2. 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
#include <algorithm>
#include <iostream>
using namespace std;
constexpr int N(2e5), LG{18};

struct pt {
  int x[2];
  int v, sum;
  int l, r;
  int L[2], R[2];
} t[N + 5], l, h;

int rt[LG];
int b[N + 5], cnt;

void upd(int p) {
  t[p].sum = t[t[p].l].sum + t[t[p].r].sum + t[p].v;
  for (int k : {0, 1}) {
    t[p].L[k] = t[p].R[k] = t[p].x[k];
    if (t[p].l) {
      t[p].L[k] = min(t[p].L[k], t[t[p].l].L[k]);
      t[p].R[k] = max(t[p].R[k], t[t[p].l].R[k]);
    }
    if (t[p].r) {
      t[p].L[k] = min(t[p].L[k], t[t[p].r].L[k]);
      t[p].R[k] = max(t[p].R[k], t[t[p].r].R[k]);
    }
  }
}

int build(int l, int r, int dep = 0) {
  int p{(l + r) >> 1};
  nth_element(b + l, b + p, b + r + 1,
              [dep](int x, int y) { return t[x].x[dep] < t[y].x[dep]; });
  int x{b[p]};
  if (l < p) t[x].l = build(l, p - 1, dep ^ 1);
  if (p < r) t[x].r = build(p + 1, r, dep ^ 1);
  upd(x);
  return x;
}

void append(int &p) {
  if (!p) return;
  b[++cnt] = p;
  append(t[p].l);
  append(t[p].r);
  p = 0;
}

int query(int p) {
  if (!p) return 0;
  bool flag{false};
  for (int k : {0, 1}) flag |= (!(l.x[k] <= t[p].L[k] && t[p].R[k] <= h.x[k]));
  if (!flag) return t[p].sum;
  for (int k : {0, 1})
    if (t[p].R[k] < l.x[k] || h.x[k] < t[p].L[k]) return 0;
  int ans{0};
  flag = false;
  for (int k : {0, 1}) flag |= (!(l.x[k] <= t[p].x[k] && t[p].x[k] <= h.x[k]));
  if (!flag) ans = t[p].v;
  return ans += query(t[p].l) + query(t[p].r);
}

int main() {
  int n;
  cin >> n;
  int lst{0};
  n = 0;
  while (true) {
    int op;
    cin >> op;
    if (op == 1) {
      int x, y, A;
      cin >> x >> y >> A;
      x ^= lst;
      y ^= lst;
      A ^= lst;
      t[++n] = {{x, y}, A};
      b[cnt = 1] = n;
      for (int sz{0};; ++sz)
        if (!rt[sz]) {
          rt[sz] = build(1, cnt);
          break;
        } else
          append(rt[sz]);
    } else if (op == 2) {
      cin >> l.x[0] >> l.x[1] >> h.x[0] >> h.x[1];
      l.x[0] ^= lst;
      l.x[1] ^= lst;
      h.x[0] ^= lst;
      h.x[1] ^= lst;
      lst = 0;
      for (int i{0}; i < LG; ++i) lst += query(rt[i]);
      cout << lst << "\n";
    } else
      break;
  }
  return 0;
}

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
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
using namespace std;
constexpr int MAXN = 200010;
int n, d[MAXN], lc[MAXN], rc[MAXN];
double ans = 2e18;

struct node {
  double x, y;
} s[MAXN];

double L[MAXN], R[MAXN], D[MAXN], U[MAXN];

double dist(int a, int b) {
  return (s[a].x - s[b].x) * (s[a].x - s[b].x) +
         (s[a].y - s[b].y) * (s[a].y - s[b].y);
}

bool cmp1(node a, node b) { return a.x < b.x; }

bool cmp2(node a, node b) { return a.y < b.y; }

void maintain(int x) {
  L[x] = R[x] = s[x].x;
  D[x] = U[x] = s[x].y;
  if (lc[x])
    L[x] = min(L[x], L[lc[x]]), R[x] = max(R[x], R[lc[x]]),
    D[x] = min(D[x], D[lc[x]]), U[x] = max(U[x], U[lc[x]]);
  if (rc[x])
    L[x] = min(L[x], L[rc[x]]), R[x] = max(R[x], R[rc[x]]),
    D[x] = min(D[x], D[rc[x]]), U[x] = max(U[x], U[rc[x]]);
}

int build(int l, int r) {
  if (l > r) return 0;
  if (l == r) {
    maintain(l);
    return l;
  }
  int mid = (l + r) >> 1;
  double avx = 0, avy = 0, vax = 0, vay = 0;  // average variance
  for (int i = l; i <= r; i++) avx += s[i].x, avy += s[i].y;
  avx /= (double)(r - l + 1);
  avy /= (double)(r - l + 1);
  for (int i = l; i <= r; i++)
    vax += (s[i].x - avx) * (s[i].x - avx),
        vay += (s[i].y - avy) * (s[i].y - avy);
  if (vax >= vay)
    d[mid] = 1, nth_element(s + l, s + mid, s + r + 1, cmp1);
  else
    d[mid] = 2, nth_element(s + l, s + mid, s + r + 1, cmp2);
  lc[mid] = build(l, mid - 1), rc[mid] = build(mid + 1, r);
  maintain(mid);
  return mid;
}

double f(int a, int b) {
  double ret = 0;
  if (L[b] > s[a].x) ret += (L[b] - s[a].x) * (L[b] - s[a].x);
  if (R[b] < s[a].x) ret += (s[a].x - R[b]) * (s[a].x - R[b]);
  if (D[b] > s[a].y) ret += (D[b] - s[a].y) * (D[b] - s[a].y);
  if (U[b] < s[a].y) ret += (s[a].y - U[b]) * (s[a].y - U[b]);
  return ret;
}

void query(int l, int r, int x) {
  if (l > r) return;
  int mid = (l + r) >> 1;
  if (mid != x) ans = min(ans, dist(x, mid));
  if (l == r) return;
  double distl = f(x, lc[mid]), distr = f(x, rc[mid]);
  if (distl < ans && distr < ans) {
    if (distl < distr) {
      query(l, mid - 1, x);
      if (distr < ans) query(mid + 1, r, x);
    } else {
      query(mid + 1, r, x);
      if (distl < ans) query(l, mid - 1, x);
    }
  } else {
    if (distl < ans) query(l, mid - 1, x);
    if (distr < ans) query(mid + 1, r, x);
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> s[i].x >> s[i].y;
  build(1, n);
  for (int i = 1; i <= n; i++) query(1, n, i);
  cout << fixed << setprecision(4) << sqrt(ans) << '\n';
  return 0;
}
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
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
constexpr int MAXN = 100010;
long long n, k;
priority_queue<long long, vector<long long>, greater<long long>> q;

struct node {
  long long x, y;
} s[MAXN];

bool cmp1(node a, node b) { return a.x < b.x; }

bool cmp2(node a, node b) { return a.y < b.y; }

long long lc[MAXN], rc[MAXN], L[MAXN], R[MAXN], D[MAXN], U[MAXN];

void maintain(int x) {
  L[x] = R[x] = s[x].x;
  D[x] = U[x] = s[x].y;
  if (lc[x])
    L[x] = min(L[x], L[lc[x]]), R[x] = max(R[x], R[lc[x]]),
    D[x] = min(D[x], D[lc[x]]), U[x] = max(U[x], U[lc[x]]);
  if (rc[x])
    L[x] = min(L[x], L[rc[x]]), R[x] = max(R[x], R[rc[x]]),
    D[x] = min(D[x], D[rc[x]]), U[x] = max(U[x], U[rc[x]]);
}

int build(int l, int r) {
  if (l > r) return 0;
  int mid = (l + r) >> 1;
  double av1 = 0, av2 = 0, va1 = 0, va2 = 0;  // average variance
  for (int i = l; i <= r; i++) av1 += s[i].x, av2 += s[i].y;
  av1 /= (r - l + 1);
  av2 /= (r - l + 1);
  for (int i = l; i <= r; i++)
    va1 += (av1 - s[i].x) * (av1 - s[i].x),
        va2 += (av2 - s[i].y) * (av2 - s[i].y);
  if (va1 > va2)
    nth_element(s + l, s + mid, s + r + 1, cmp1);
  else
    nth_element(s + l, s + mid, s + r + 1, cmp2);
  lc[mid] = build(l, mid - 1);
  rc[mid] = build(mid + 1, r);
  maintain(mid);
  return mid;
}

long long sq(long long x) { return x * x; }

long long dist(int a, int b) {
  return max(sq(s[a].x - L[b]), sq(s[a].x - R[b])) +
         max(sq(s[a].y - D[b]), sq(s[a].y - U[b]));
}

void query(int l, int r, int x) {
  if (l > r) return;
  int mid = (l + r) >> 1;
  long long t = sq(s[mid].x - s[x].x) + sq(s[mid].y - s[x].y);
  if (t > q.top()) q.pop(), q.push(t);
  long long distl = dist(x, lc[mid]), distr = dist(x, rc[mid]);
  if (distl > q.top() && distr > q.top()) {
    if (distl > distr) {
      query(l, mid - 1, x);
      if (distr > q.top()) query(mid + 1, r, x);
    } else {
      query(mid + 1, r, x);
      if (distl > q.top()) query(l, mid - 1, x);
    }
  } else {
    if (distl > q.top()) query(l, mid - 1, x);
    if (distr > q.top()) query(mid + 1, r, x);
  }
}

int main() {
  cin >> n >> k;
  k *= 2;
  for (int i = 1; i <= k; i++) q.push(0);
  for (int i = 1; i <= n; i++) cin >> s[i].x >> s[i].y;
  build(1, n);
  for (int i = 1; i <= n; i++) query(1, n, i);
  cout << q.top() << endl;
  return 0;
}

Practice problems

[SDOI2010] Hide and Seek

[Violet] Angel Doll / SJY Places Pieces

[Chinese national training team] JZPFAR

[BOI2007] Mokia

Luogu P4475 Chocolate Kingdom

[CH Weak Provinces Mutual Test R2] TATT