AIOJ

Introduction

Prerequisites: heavy-light decomposition

The time complexity of heavy-light decomposition is $O(n\log^2 n)$ . Although the familiar LCT has time complexity $O(n\log n)$ , its constant factor is large, so it may even be slower than heavy-light decomposition. Is there a method that is still $O(n\log n)$ but has a relatively small constant factor? This is where the global balanced binary tree comes in.

A global balanced binary tree is actually a forest of binary trees, where each binary tree maintains one heavy path. However, the binary trees in this forest are connected to one another: the root of each binary tree points to the parent of the top node of its heavy path, just as in an LCT. Unlike an LCT, a global balanced binary tree is static; the shape of the tree does not change after construction.

A global balanced binary tree is a data structure that can handle path updates and queries on a tree. It supports:

Updating an entire path in $O(\log n)$ time.
Querying an entire path in $O(\log n)$ time.
Finding the lowest common ancestor, updating a subtree, querying a subtree, and similar operations in $O(\log n)$ time; these complexities are the same as for heavy-light decomposition.

Main properties

A global balanced binary tree is composed of many binary trees connected by light edges. Each binary tree maintains one heavy path of the original tree, and its in-order traversal is the order of increasing depth along that heavy path. Each node appears in exactly one binary tree.
Edges are divided into heavy edges and light edges. A heavy edge is contained in a binary tree and is maintained like an ordinary binary tree, with left child, right child, and parent recorded. A light edge goes from the root of one binary tree to the parent of the top node of its corresponding heavy path. When maintaining a light edge, the parent is recognized but the child is not: it can be traversed only from the child to the parent, not in the reverse direction. Edges in the global balanced binary tree do not correspond one-to-one with edges in the original tree.
Counting both heavy and light edges, the height of a global balanced binary tree is $O(\log n)$ . This property guarantees the time complexity of the global balanced binary tree.

Here is an example of building a global balanced binary tree. The first diagram is the original tree, rooted at node 1. Solid lines are heavy edges.

global-bst-1

The second diagram is the constructed global balanced binary tree. Dashed lines are light edges, solid lines are heavy edges, and each binary tree is marked with a red circle.

global-bst-2

Building the tree

First, as in ordinary heavy-light decomposition, run one DFS to find the heavy child of every node. Starting from the root, find the heavy path containing the root; recursively build trees for the light children of these vertices and connect the light edges. Then build a binary tree for the heavy path. Store the vertices on the heavy path in an array, and compute for each vertex the sum of the sizes of its light-child subtrees plus one (the size contributed by the vertex itself). Use these values to find the weighted midpoint of the heavy path, make it the root of the binary tree, recursively build both sides, and connect them with heavy edges.

The code is as follows:

Implementation

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 from the points in [bl, br) of b and return its 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;
  }
  // find the bs-weighted midpoint by binary search
  y = b[x];
  ss[y] = br - bl;  // ss: the 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 the tree and connect the light edge; connect from the binary-tree root, not from the child
  while (y = son[y]);
  y = 0;
  do {
    b[y++] = x;                              // store the points on the heavy chain
    bs[y] = bs[y - 1] + sz[x] - sz[son[x]];  // bs: sum of light-child sizes + 1; compute prefix sums
  } while (x = son[x]);
  return cbuild(0, y);
}

The time complexity of building the tree is $O(n\log n)$ , as can be seen from the code. We can then prove that the height is $O(\log n)$ : consider jumping from an arbitrary vertex through parent pointers to the root. Jumping across a light edge corresponds to moving to another heavy path in the original tree, so by the properties of heavy-light decomposition there are at most $O(\log n)$ light edges. Because the root chosen while building each binary tree is the weighted midpoint by light-child size, one jump across a heavy edge at least doubles the total size of light children, so there are also at most $O(\log n)$ heavy edges. Thus the overall height is $O(\log n)$ .

Queries

That covers the global balanced binary tree. The remaining path-update and path-query operations are relatively simple: start from the point to operate on and repeatedly jump to the root. Operating on all points on the same heavy path that are shallower than the target point is equivalent to operating on all nodes to the left of the target node in the binary tree for that heavy path. These operations can be decomposed into a sequence of subtree operations, similarly to maintaining an ordinary binary tree; this involves maintaining subtree sums and applying subtree tags. Here, tags are made persistent. One can also apply tags with pushdown and maintain subtree sums with pushup, but this may be more complicated: ordinary binary-tree operations are usually performed top-down, whereas here the jump path must first be determined and pushdown must then be performed from top to bottom, which may lead to a larger constant factor.

The code is as follows:

Implementation

// a：subtree-add tag
// s：subtree sum (excluding the add tag)
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 crossing 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 crossing a light edge
    x = f[x];
  }
  return ret;
}

For subtree operations, the light children must also be considered, so one must additionally maintain a subtree sum and subtree tag that include the light children. See P3384 (template) Heavy-Light Decomposition.

Example

??? note "P4751 (Template) "Dynamic DP" & Dynamic Tree Divide and Conquer (Enhanced Version)" ```cpp #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];  // maintain two matrices for each point

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-child 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 ordinary DP array
    f[u][1] += f[v][0];
    g[u][0] += max(f[v][0], f[v][1]);  // g[][] only stores information about the node itself and its light children
    g[u][1] += f[v][0];
  }
}

void PushUp(int u) {
  matr2[u] = matr1[u];  // matr1 is the information for one point plus its light children; matr2 is interval information
  if (bstch[u][0]) matr2[u] = matr2[bstch[u][0]] * matr2[u];
  // note the direction of the transition; it may differ 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)  // the centroid has been found
    {
      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 the 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 is a light child
      {
        int v = p->to, ret = Build(v);
        trfa[ret] = pos;  // attach the light child's treefa[]
      }
  tp = 0;
  for (int pos = u; pos; pos = son[pos]) stk[++tp] = pos;  // extract the heavy chain
  int ret = SBuild(1, tp);  // run SBuild separately on the heavy chain (I assume this means Special Build?)
  return ret;               // return the root of the binary tree for the current heavy chain
}

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 the heavy child
  DFS2(1, -1);
  // find the initial DP values; this could also be done in Build(), but writing it this way matches the tree-decomposition implementation
  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 the matrix
  }
  root = Build(1);  // root is the centroid of the heavy chain containing the root node
  int lastans = 0;
  for (int i = 1; i <= m; i++) {
    u = read(), v = read();
    u ^= lastans;  // force online
    Modify(u, v);
    lastans = getmx1(root);  // read the value directly
    if (lastans == 0)
      putchar('0');
    else
      print(lastans);
    putchar('\n');
  }
  return 0;
}
```

References

P4211 [LNOI2014] LCA | Global Balanced Binary Tree