Skip to content

Globally Balanced Binary Tree

Introduction

Prerequisite knowledge: Heavy-Light Decomposition (HLD)

Since the time complexity of HLD is \(O(n\log^2 n)\), while the well-known LCT (Link-Cut Tree) has a time complexity of \(O(n\log n)\) but with a large constant factor, it might even be slower than HLD. So, is there a method that is both \(O(n\log n)\) and has a relatively small constant factor? This is where the Global Balanced Binary Tree (GBST) comes in.

The Global Balanced Binary Tree is essentially a forest of binary trees, where each binary tree maintains a heavy path. However, the binary trees in this forest are interconnected: the root of each binary tree is linked to the parent of the top node of its corresponding heavy path, similar to LCT. But unlike LCT, the GBST is a static tree—its structure does not change after construction.

The Global Balanced Binary Tree is a data structure that can handle path modifications/queries on trees, achieving:

  • \(O(\log n)\) for modifying an entire path.
  • \(O(\log n)\) for querying an entire path.
  • \(O(\log n)\) for operations like finding the lowest common ancestor, subtree modifications, and subtree queries. These complexities are the same as in heavy-light decomposition.

Key Properties

  1. The Global Balanced Binary Tree consists of many binary trees connected by light edges. Each binary tree maintains a heavy path from the original tree, with its in-order traversal corresponding to the monotonically increasing depth order along that heavy path. Each node appears in exactly one binary tree.
  2. Edges are classified as heavy edges and light edges. Heavy edges are those within a binary tree, maintained like a normal binary tree by recording left child, right child, and parent node. Light edges connect the root of a binary tree to the parent of the top node of its corresponding heavy path. Light edges are maintained with "parent recognition only," meaning a child can access its parent but not vice versa. Note that edges in the GBST do not correspond directly to edges in the original tree.
  3. Including both heavy and light edges, the height of the Global Balanced Binary Tree is \(O(\log n)\). This property ensures the time complexity of the GBST.

Below is an example of constructing a Global Balanced Binary Tree. The first diagram is the original tree with node 1 as the root. Solid lines represent heavy edges.

global-bst-1

The second diagram shows the constructed Global Balanced Binary Tree. Dashed lines are light edges, solid lines are heavy edges, and each binary tree is indicated by a red circle.

global-bst-2

Construction

First, perform a DFS to find the heavy son of each node, just like in standard heavy-light decomposition. Then, starting from the root, identify the heavy path containing the root. Recursively build trees for the light sons of nodes on this path and connect them with light edges. Next, construct a binary tree for the nodes on the heavy path. Store the nodes of the heavy path in an array and compute for each node the sum of the subtree sizes of its light sons plus one (i.e., the contribution of the node itself). Then, find the weighted midpoint of this heavy path based on these values, use it as the root of the binary tree, recursively build the left and right subtrees, and connect them with heavy edges.

Here is the code:

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
std::vector<int> G[N];
int n, fa[N], son[N], sz[N];

void dfsS(int u) {
  sz[u] = 1;
  for (int v : G[u]) {
    dfsS(v);
    sz[u] += sz[v];
    if (sz[v] > sz[son[u]]) son[u] = v;
  }
}

int b[N], bs[N], l[N], r[N], f[N], ss[N];

// Build a binary tree for points in b[bl, br) and return the root
int cbuild(int bl, int br) {
  int x = bl, y = br;
  while (y - x > 1) {
    int mid = (x + y) >> 1;
    if (2 * (bs[mid] - bs[bl]) <= bs[br] - bs[bl])
      x = mid;
    else
      y = mid;
  }
  // Binary search to find the weighted midpoint according to bs
  y = b[x];
  ss[y] = br - bl;  // ss: size of the heavy subtree in the binary tree
  if (bl < x) {
    l[y] = cbuild(bl, x);
    f[l[y]] = y;
  }
  if (x + 1 < br) {
    r[y] = cbuild(x + 1, br);
    f[r[y]] = y;
  }
  return y;
}

int build(int x) {
  int y = x;
  do
    for (int v : G[y])
      if (v != son[y])
        f[build(v)] =
            y;  // Recursively build trees and connect light edges.
                // Note: connect from the root of the binary tree, not from the son.
  while (y = son[y]);
  y = 0;
  do {
    b[y++] = x;                              // Store nodes on the heavy path
    bs[y] = bs[y - 1] + sz[x] - sz[son[x]];  // bs: sum of light son sizes + 1, prefix sum
  } while (x = son[x]);
  return cbuild(0, y);
}

From the code, we can see the construction time complexity is \(O(n\log n)\). Next, we can prove the tree height is \(O(\log n)\): consider jumping from any node to the root via parent pointers. Jumping a light edge corresponds to moving to another heavy path in the original tree; by the properties of heavy-light decomposition, there are at most \(O(\log n)\) light edge jumps. Since the root of each binary tree is chosen as the weighted midpoint considering light sons, jumping a heavy edge at least doubles the total size including light sons, so there are also at most \(O(\log n)\) heavy edge jumps. Thus, the overall tree height is \(O(\log n)\).

Queries

The above covers the construction of the Global Balanced Binary Tree. The remaining operations for path modification and query are relatively straightforward. Starting from the node to be operated on, keep jumping to the root. Operating on all nodes on the same heavy path with depth less than the target node essentially corresponds to operating on all nodes to the left of the target node in the binary tree of that heavy path. These operations can be decomposed into a series of subtree operations, similar to maintaining a normal binary tree, involving maintaining subtree sums and applying subtree tags. In this process, permanent marking is used. Alternatively, one could use pushdown to propagate tags and pushup to maintain subtree sums, but this might be more complex because typically binary tree operations are top-down, whereas here the jump path must be determined first before pushing down from top to bottom, which could lead to a larger constant factor.

Here is the code:

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
32
33
34
35
36
37
38
// a: subtree addition tag
// s: subtree sum (excluding addition tags)
int a[N], s[N];

void add(int x) {
  bool t = true;
  int z = 0;
  while (x) {
    s[x] += z;
    if (t) {
      a[x]++;
      if (r[x]) a[r[x]]--;
      z += 1 + ss[l[x]];
      s[x] -= ss[r[x]];
    }
    t = (x != l[f[x]]);
    if (t && x != r[f[x]]) z = 0;  // Clear when skipping a light edge
    x = f[x];
  }
}

int query(int x) {
  int ret = 0;
  bool t = true;
  int z = 0;
  while (x) {
    if (t) {
      ret += s[x] - s[r[x]];
      ret -= 1ll * ss[r[x]] * a[r[x]];
      z += 1 + ss[l[x]];
    }
    ret += 1ll * z * a[x];
    t = (x != l[f[x]]);
    if (t && x != r[f[x]]) z = 0;  // Clear when skipping a light edge
    x = f[x];
  }
  return ret;
}

Additionally, for subtree operations, which involve light sons, one needs to maintain subtree sums and tags including light sons. This can be practiced with "P3384【Template】Heavy-Light Decomposition".

Example Problems

P4751【Template】"Dynamic DP" & Dynamic Tree Divide and Conquer (Enhanced Version) 
  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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include <algorithm>
#include <cstdio>
#include <cstring>
constexpr int MAXN = 1000000;
constexpr int MAXM = 3000000;
constexpr int INF = 0x3FFFFFFF;
using namespace std;

struct edge {
  int to;
  edge *nxt;
} edges[MAXN * 2 + 5];

edge *ncnt = &edges[0], *Adj[MAXN + 5];
int n, m;

struct Matrix {
  int M[2][2];

  Matrix operator*(const Matrix &B) const {
    static Matrix ret;
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++) {
        ret.M[i][j] = -INF;
        for (int k = 0; k < 2; k++)
          ret.M[i][j] = max(ret.M[i][j], M[i][k] + B.M[k][j]);
      }
    return ret;
  }
} matr1[MAXN + 5], matr2[MAXN + 5];  // Each node maintains two matrices

int root;
int w[MAXN + 5], dep[MAXN + 5], son[MAXN + 5], siz[MAXN + 5], lsiz[MAXN + 5];
int g[MAXN + 5][2], f[MAXN + 5][2], trfa[MAXN + 5], bstch[MAXN + 5][2];
int stk[MAXN + 5], tp;
bool vis[MAXN + 5];

void AddEdge(int u, int v) {
  edge *p = ++ncnt;
  p->to = v;
  p->nxt = Adj[u];
  Adj[u] = p;

  edge *q = ++ncnt;
  q->to = u;
  q->nxt = Adj[v];
  Adj[v] = q;
}

void DFS(int u, int fa) {
  siz[u] = 1;
  for (edge *p = Adj[u]; p != NULL; p = p->nxt) {
    int v = p->to;
    if (v == fa) continue;
    dep[v] = dep[u] + 1;
    DFS(v, u);
    siz[u] += siz[v];
    if (!son[u] || siz[son[u]] < siz[v]) son[u] = v;
  }
  lsiz[u] = siz[u] - siz[son[u]];  // Sum of light son sizes + 1
}

void DFS2(int u, int fa) {
  f[u][1] = w[u], f[u][0] = 0;
  g[u][1] = w[u], g[u][0] = 0;
  if (son[u]) {
    DFS2(son[u], u);
    f[u][0] += max(f[son[u]][0], f[son[u]][1]);
    f[u][1] += f[son[u]][0];
  }
  for (edge *p = Adj[u]; p != NULL; p = p->nxt) {
    int v = p->to;
    if (v == fa || v == son[u]) continue;
    DFS2(v, u);
    f[u][0] += max(f[v][0], f[v][1]);  // f[][] is the normal DP array
    f[u][1] += f[v][0];
    g[u][0] += max(f[v][0], f[v][1]);  // g[][] only includes the node itself and light sons
    g[u][1] += f[v][0];
  }
}

void PushUp(int u) {
  matr2[u] = matr1[u];  // matr1 is the node's own info plus light sons, matr2 is interval info
  if (bstch[u][0]) matr2[u] = matr2[bstch[u][0]] * matr2[u];
  // Note the direction of multiplication, but this may vary if matrix multiplication is defined differently
  if (bstch[u][1]) matr2[u] = matr2[u] * matr2[bstch[u][1]];
}

int getmx2(int u) { return max(matr2[u].M[0][0], matr2[u].M[0][1]); }

int getmx1(int u) { return max(getmx2(u), matr2[u].M[1][0]); }

int SBuild(int l, int r) {
  if (l > r) return 0;
  int tot = 0;
  for (int i = l; i <= r; i++) tot += lsiz[stk[i]];
  for (int i = l, sumn = lsiz[stk[l]]; i <= r; i++, sumn += lsiz[stk[i]])
    if (sumn * 2 >= tot)  // Found the centroid
    {
      int lch = SBuild(l, i - 1), rch = SBuild(i + 1, r);
      bstch[stk[i]][0] = lch;
      bstch[stk[i]][1] = rch;
      trfa[lch] = trfa[rch] = stk[i];
      PushUp(stk[i]);  // Aggregate interval information
      return stk[i];
    }
  return 0;
}

int Build(int u) {
  for (int pos = u; pos; pos = son[pos]) vis[pos] = true;
  for (int pos = u; pos; pos = son[pos])
    for (edge *p = Adj[pos]; p != NULL; p = p->nxt)
      if (!vis[p->to])  // It's a light son
      {
        int v = p->to, ret = Build(v);
        trfa[ret] = pos;  // Connect the light son's treefa[]
      }
  tp = 0;
  for (int pos = u; pos; pos = son[pos]) stk[++tp] = pos;  // Extract the heavy path
  int ret = SBuild(1, tp);  // Perform SBuild on the heavy path (I guess Special Build?)
  return ret;               // Return the root of the binary tree for this heavy path
}

void Modify(int u, int val) {
  matr1[u].M[1][0] += val - w[u];
  w[u] = val;
  for (int pos = u; pos; pos = trfa[pos])
    if (trfa[pos] && bstch[trfa[pos]][0] != pos && bstch[trfa[pos]][1] != pos) {
      matr1[trfa[pos]].M[0][0] -= getmx1(pos);
      matr1[trfa[pos]].M[0][1] = matr1[trfa[pos]].M[0][0];
      matr1[trfa[pos]].M[1][0] -= getmx2(pos);
      PushUp(pos);
      matr1[trfa[pos]].M[0][0] += getmx1(pos);
      matr1[trfa[pos]].M[0][1] = matr1[trfa[pos]].M[0][0];
      matr1[trfa[pos]].M[1][0] += getmx2(pos);
    } else
      PushUp(pos);
}

int read() {
  int ret = 0, f = 1;
  char c = 0;
  while (c < '0' || c > '9') {
    c = getchar();
    if (c == '-') f = -f;
  }
  ret = 10 * ret + c - '0';
  while (true) {
    c = getchar();
    if (c < '0' || c > '9') break;
    ret = 10 * ret + c - '0';
  }
  return ret * f;
}

void print(int x) {
  if (x == 0) return;
  print(x / 10);
  putchar(x % 10 + '0');
}

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) w[i] = read();
  int u, v;
  for (int i = 1; i < n; i++) {
    u = read(), v = read();
    AddEdge(u, v);
  }
  DFS(1, -1);
  // Find heavy sons
  DFS2(1, -1);
  // Compute initial DP values; can also be done inside Build(), but this way aligns with HLD style
  for (int i = 1; i <= n; i++) {
    matr1[i].M[0][0] = matr1[i].M[0][1] = g[i][0];
    matr1[i].M[1][0] = g[i][1], matr1[i].M[1][1] = -INF;  // Initialize matrices
  }
  root = Build(1);  // root is the centroid of the heavy path containing the root
  int lastans = 0;
  for (int i = 1; i <= m; i++) {
    u = read(), v = read();
    u ^= lastans;  // Force online
    Modify(u, v);
    lastans = getmx1(root);  // Directly get the value
    if (lastans == 0)
      putchar('0');
    else
      print(lastans);
    putchar('\n');
  }
  return 0;
}

References

P4211 [LNOI2014] LCA | Global Balanced Binary Tree

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