Skip to content

Partition Tree

Introduction

A Dividing Tree is a data structure used to solve the problem of finding the \(K\)-th largest element in an interval. Its constant factor and difficulty of understanding are much lower than those of a Chairman Tree. At the same time, the Dividing Tree is closely related to the "K-th largest" problem, so it is a data structure based on sorting.

Prerequisite knowledge: Chairman Tree

Process

Building the Tree

Building a Dividing Tree is relatively simple compared to other trees, but still somewhat complex.

As shown in the figure, each layer has an array that appears unordered. In fact, every number marked in red is to be assigned to the left child. What is the rule for assignment? It is compared with the median of this layer. If it is less than or equal to the median, it goes to the left; otherwise, it goes to the right. However, note that it is not strictly "less than or equal to goes left, otherwise goes right". This is because the median may have duplicates, and it also depends on the parity of \(N\). The following code demonstrates a clever approach; you can refer to the code.

We cannot sort each layer every time; not only would the constant factor be high, but even the theoretical complexity would be unacceptable. Consider finding the median: one sorting operation is enough. Why? For example, to find the median of \(l,r\), it is essentially num[mid] after sorting.

Two key arrays:

tree[log(N),N]: The tree itself, storing all values, with space complexity \(O(n\log n)\). toleft[log(N),n]: The number of elements from 1 to i that go to the left child in each layer. This is a prefix sum and requires some understanding.

Implementation 
 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
procedure Build(left,right,deep:longint); // left,right represent the interval endpoints, deep is the layer
var
  i,mid,same,ls,rs,flag:longint; // flag is used to balance the number of elements on left and right
begin
  if left=right then exit; // reached the bottom layer
  mid:=(left+right) >> 1;
  same:=mid-left+1;
  for i:=left to right do 
    if tree[deep,i]<num[mid] then
      dec(same);

  ls:=left; // pointer to the first element of the left child
  rs:=mid+1; // pointer to the first element of the right child
  for i:=left to right do
  begin
    flag:=0;
    if (tree[deep,i]<num[mid])or((tree[deep,i]=num[mid])and(same>0)) then // condition to assign to left
    begin
      flag:=1; tree[deep+1,ls]:=tree[deep,i]; inc(ls);
      if tree[deep,i]=num[mid] then // balance left and right counts
        dec(same);
    end
    else
    begin
      tree[deep+1,rs]:=tree[deep,i]; inc(rs);
    end;
    toleft[deep,i]:=toleft[deep,i-1]+flag;
  end;
  Build(left,mid,deep+1); // continue recursively
  Build(mid+1,right,deep+1);
end;

Query

First, let's briefly recall the Chairman Tree. When finding the \(K\)-th smallest element in an interval with a Chairman Tree, we use \(K\) as the benchmark: go left if possible, otherwise go right and subtract the left count. The same principle applies to the Dividing Tree.

The tricky part of the query is interval narrowing. In the figure below, the query is from \(3\) to \(7\), so the next layer only needs to query \(2\) to \(3\). We define \([\text{left},\text{right}]\) as the narrowed interval (target interval), while \([l,r]\) remains the interval of the current node. Why mark the target interval? Because it is the benchmark for determining whether the answer lies on the left or right.

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function Query(left,right,k,l,r,deep:longint):longint;
var
  mid,x,y,cnt,rx,ry:longint;
begin
  if left=right then // writing l=r is also fine, as the target interval must contain the answer
    exit(tree[deep,left]);
  mid:=(l+r) >> 1;
  x:=toleft[deep,left-1]-toleft[deep,l-1]; // number of elements from l to left-1 that went to the left child
  y:=toleft[deep,right]-toleft[deep,l-1]; // number of elements from l to right that went to the left child
  ry:=right-l-y; rx:=left-l-x; // ry: number of elements from l to right that went to the right child; rx: number from l to left-1 that went to the right child
  cnt:=y-x; // number of left child elements from left to right
  if cnt>=k then // common sense in Chairman Tree
    Query:=Query(l+x,l+y-1,k,l,mid,deep+1) // l+x narrows the left boundary, l+y-1 narrows the right boundary. For the figure above, this means discarding nodes 1 and 2.
  else
    Query:=Query(mid+rx+1,mid+ry+1,k-cnt,mid+1,r,deep+1); // similarly narrow the interval, but to the right side. Note to subtract cnt from k.
end;

Properties

Time complexity: A single query takes \(O(\log n)\), so \(m\) queries take \(O(m\log n)\).

Space complexity: Only \(O(n\log n)\) numbers need to be stored.

Test results: Chairman Tree: \(1482 \text{ms}\), Dividing Tree: \(889 \text{ms}\) (non-recursive, relatively small constant).

Applications of Dividing Tree

Example problem: Luogu P3157[CQOI2011] Dynamic Inversion Pairs

Brief description: Given a permutation of \(n\) elements (\(n\leq 10^5\)), there are m queries (\(m\leq 5\times 10^4\)). After each query, delete a number from the permutation and find the number of inversion pairs in the permutation after deletion.

This problem can be solved using CDQ in \(\Theta(n\log^2n)\) time and \(\Theta(n)\) space, and CDQ also has excellent constant factors.

If the problem is changed to force online queries, a common solution uses a Fenwick Tree + Chairman Tree (tree of trees), with time complexity \(\Theta(n\log^2n)\), space complexity \(\Theta(n\log^2n)\), and a relatively large constant, but it can still pass this problem.

Using a Dividing Tree, this problem can be solved online in \(\Theta(n\log^2n)\) time and \(\Theta(n\log n)\) space, with a much smaller constant compared to the tree-of-trees solution (roughly comparable to CDQ).

Note

For programming convenience, this article divides large arrays into two smaller arrays based on the median of positions. That is, the Dividing Tree here is equivalent to the process of merge sort, not quicksort. The top layer is a sorted array, and the bottom layer is the original array.

For each node in the Dividing Tree, we call it a right node if and only if it will be assigned to the right child in the next layer, i.e., numbers with relatively later positions in the original array. Similarly, we can define left nodes. If the top layer is sorted during construction, similar to using merge sort to count inversion pairs, we can find that the number of inversion pairs in an array is the sum of the number of right nodes before each left node.

Now consider deletion operations. Deleting a left node reduces the total inversion pairs by the number of right nodes before it, while deleting a right node reduces the inversion pairs by the number of left nodes after it. Thus, we can dynamically maintain "the number of right nodes before each left node" and "the number of left nodes after each right node". This can be easily maintained using a Fenwick Tree.

Note that when using a Fenwick Tree for maintenance, we can only compute contributions within the same block of the Dividing Tree and cannot cross block boundaries. There is a clever way to handle this with a Fenwick Tree.

Consider that the index range of each block in the Dividing Tree must be of the form \([c\times 2^k+1,(c+1)\times 2^k]\), as listed below (since the code does not involve processing the bottom layer of the Dividing Tree, only enumerating down to the second-to-last layer):

1
2
3
4
[0001 0010] [0011 0100] [0101 0110] [0111 1000] [1001 1010] [1011 1100] [1101 1110] [1111 10000]  lev=1
[0001 0010 0011 0100]   [0101 0110 0111 1000]   [1001 1010 1011 1100]   [1101 1110 1111 10000]    lev=2
[0001 0010 0011 0100 0101 0110 0111 1000]       [1001 1010 1011 1100 1101 1110 1111 10000]        lev=3
[0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 10000]                lev=4

Recall the principle of Fenwick Tree: when jumping upward, we do x += lowbit(x). If we can ensure not to jump out of the block while jumping upward, we can guarantee that only elements within the block are affected. Similarly for upward queries.

To ensure not to jump out of the block while jumping upward, it is sufficient to ensure that \(lowbit(x)<2^{lev}\) during the jump.

Downward jumps are handled completely differently. If the indices of each block are represented using 0-index notation, they are of the form \([c\times 2^k,(c+1)\times 2^k)\). Then, simply right-shift an index value by k to determine which block it belongs to. During downward jumps, continuously check whether the jump crosses block boundaries.

Note that the maximum index accessed by the Fenwick Tree implemented this way is the nearest power of two to n, so the array size cannot be set to n.

Since modifications are required in \(\log n\) layers, and the time complexity for modification at layer \(k\) is \(\Theta(k)\), the final time complexity is \(\Theta(n\log n+m\log^2n)\).

Attached 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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <algorithm>
#include <cstring>
#include <iostream>
#if defined(_MSC_VER) && !defined(__clang__)
#include <immintrin.h>
#define __builtin_clz _lzcnt_u32
#endif
using namespace std;
using lld = long long;

int ti[2][17][131073];

int lowbit(int x) { return x & (-x); }

void fixup(int k, int x) {
  for (; lowbit(x) < 1 << k; x += lowbit(x)) {
    ++ti[0][k - 1][x];
  }
  ++ti[0][k - 1][x];
}

void fixdown(int k, int x) {
  for (; ((x ^ lowbit(x)) - 1) >> k == (x - 1) >> k; x ^= lowbit(x)) {
    ++ti[1][k - 1][x];
  }
  ++ti[1][k - 1][x];
}

int queryup(int k, int x) {
  int res = 0;
  for (; lowbit(x) < 1 << k; x += lowbit(x)) {
    res += ti[1][k - 1][x];
  }
  return res + ti[1][k - 1][x];
}

int querydown(int k, int x) {
  int res = 0;
  for (; ((x ^ lowbit(x)) - 1) >> k == (x - 1) >> k; x ^= lowbit(x)) {
    res += ti[0][k - 1][x];
  }
  return res + ti[0][k - 1][x];
}

int ai[100005];
int tx[100005];

lld mgx(int* npi, int* nai, int* rxi, int* lxi, int al, int ar, int bl,
        int br) {
  int rx = 1;
  int lx = ar - al;
  lld res = 0;
  for (; al != ar || bl != br; ++npi, ++nai, ++rxi, ++lxi) {
    if (al != ar && (bl == br || tx[al] < tx[bl])) {
      --lx;
      *rxi = rx;
      *nai = tx[al];
      *npi = al;
      ++al;
    } else {
      ++rx;
      *lxi = lx;
      res += ar - al;
      *nai = tx[bl];
      *npi = bl;
      ++bl;
    }
  }
  return res;
}

int npi[1700005];
int nri[1700005];
int nli[1700005];

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> ai[i];

  if (n == 1) {
    for (int i = 1; i <= m; ++i) cout << "0\n";
    return 0;
  }

  const int logn = 31 - __builtin_clz(n - 1);

  lld ans = 0;
  for (int i = logn; i >= 0; --i) {
    memcpy(tx, ai, (n + 1) * sizeof(int));
    for (int j = 1; j <= n; j += 1 << (logn - i + 1)) {
      ans += mgx(npi + n * i + j, ai + j, nri + n * i + j, nli + n * i + j, j,
                 min(n + 1, j + (1 << (logn - i))),
                 min(n + 1, j + (1 << (logn - i))),
                 min(n + 1, j + (1 << (logn - i + 1))));
    }
  }
  cout << ans << '\n';

  for (int asdf = 1; asdf < m; ++asdf) {
    int x;
    cin >> x;
    for (int i = 0, p = 0; i <= logn; ++i, p += n) {
      if (nri[p + x]) {
        ans -= nri[p + x] - querydown(logn - i + 1, x) - 1;
        fixdown(logn - i + 1, x);
      } else {
        ans -= nli[p + x] - queryup(logn - i + 1, x);
        fixup(logn - i + 1, x);
      }
      x = npi[p + x];
    }
    cout << ans << '\n';
  }
}

Afterword

Reference blog: Link.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用