Official

A - セグメント木/Segment Tree Editorial by maspy

[1] What is a segment tree?

A segment tree is a data structure for efficiently processing range queries on a sequence. In this problem, it supports updates to \(1\) element and range minimum queries, each in \(O(\log N)\) time.

In a segment tree, each node of a complete binary tree stores information about a certain interval. Here, each node stores the minimum value in its interval.

The key is the following invariant:

  • Each leaf stores an element of the sequence \(A\).
  • Each non-leaf node stores the minimum of the values stored in its \(2\) children.

An invariant is a property that a data structure must always satisfy. Keeping invariants in mind is important when designing an implementation or proving its correctness, both for segment trees and for other data structures.

Keep this invariant in mind when implementing the segment tree described in the next section.

[2] Implementing a segment tree

[2.1] Segment tree indices

To implement a segment tree, assign an integer index to each node of the complete binary tree.

  • The root has index \(1\).
  • The children of node \(i\) have indices \(2i,2i+1\).
  • The parent of node \(i\) has index \(\lfloor i/2\rfloor\).

When implementing a tree structure, pointers or similar mechanisms are often used to maintain parent-child relationships. In a segment tree, however, the indices of a node’s parent and children can be computed directly from its index. This allows an implementation using only arrays, making the code concise and fast.

For a sequence of length \(N\), set the number of leaves of the complete binary tree to seg_size, the smallest power of \(2\) that is at least \(N\).

If the information for each node is stored in an array dat, the original element A[i] corresponds to dat[seg_size+i].

Below, sequence indices start at \(0\), and we assume that dat and seg_size have already been defined. Also, let INF be an integer greater than every element value that can occur in this problem.

[2.2] Initial construction and point updates

For initial construction, assign the initial values to the leaves, then compute the value of each node from the bottom up.

void build(const vector<int>& A) {
  int N = A.size();
  seg_size = 1;
  while (seg_size < N) seg_size *= 2;

  // Assign values to the leaves
  for (int i = 0; i < seg_size; ++i) {
    dat[seg_size + i] = (i < N ? A[i] : INF);
  }

  // Compute the value of each node from the bottom up
  for (int i = seg_size - 1; i >= 1; --i) {
    dat[i] = min(dat[2 * i], dat[2 * i + 1]);
  }
}

To make the number of leaves a power of \(2\), assign INF to the extra leaves.

There are \(O(N)\) leaves and \(O(N)\) nodes in the entire complete binary tree, so initial construction takes \(O(N)\) time.

For an update to \(1\) element, overwrite the value of the corresponding leaf, then recompute its ancestors in order.

void point_set(int i, int x) {
  i += seg_size;
  dat[i] = x;

  while (i > 1) {
    // Move to the parent and recompute its value to maintain the invariant
    i /= 2;
    dat[i] = min(dat[2 * i], dat[2 * i + 1]);
  }
}

Recomputing only the ancestors of the modified leaf preserves the invariant in [1].

Since the height of the complete binary tree is \(O(\log N)\), an update to \(1\) element also takes \(O(\log N)\) time.

Thus, initial construction and updates to \(1\) element are relatively easy to implement once you understand the parent-child index relationships and the invariant.

Next, consider range minimum queries. Here, we implement a function prod(L,R) that returns the minimum value in the half-open interval \([L,R)\).

We introduce \(2\) main implementation approaches: one using recursion and one without recursion.

[2.3] A recursive implementation of range queries

In a recursive implementation, pass the interval represented by each node as function arguments.

Suppose node \(i\) represents \([\mathrm{node\_L},\mathrm{node\_R})\) and the queried interval is \([L,R)\). Depending on how these intervals relate, there are \(3\) cases:

  1. The intervals do not intersect: Return INF.
  2. \([\mathrm{node\_L},\mathrm{node\_R})\) is contained in \([L,R)\): Return dat[i].
  3. Otherwise: Recursively examine the left and right children and return the minimum of their results.

Implementing this approach directly gives the following:

// Node i represents the interval [node_L, node_R)
// Return the minimum over the intersection of [node_L, node_R) and [L, R)
int prod_rec(int i, int node_L, int node_R, int L, int R) {
  // No intersection
  if (node_R <= L || R <= node_L) return INF;

  // The whole interval of this node is contained in the query
  if (L <= node_L && node_R <= R) return dat[i];

  // Process the left and right children recursively
  int m = (node_L + node_R) / 2;
  int x = prod_rec(2 * i, node_L, m, L, R);
  int y = prod_rec(2 * i + 1, m, node_R, L, R);
  return min(x, y);
}

int prod(int L, int R) {
  return prod_rec(1, 0, seg_size, L, R);
}

When the queried interval completely contains the interval represented by a node, this implementation uses that node’s value and does not explore any further.

In other words, it decomposes the queried interval into intervals represented by several nodes and takes the minimum of their values.

Only nodes whose intervals straddle one of the boundaries of \([L,R)\) are recursively split. At any fixed depth there are at most \(2\) such nodes, so the time complexity is \(O(\log N)\).

[2.4] An iterative implementation of range queries

We can also process the interval from its left and right ends without recursion.

First, add seg_size to L and R to convert them to leaf indices. Then move up to the parent level, selecting the necessary nodes at the ends of the interval.

int prod(int L, int R) {
  L += seg_size;
  R += seg_size;

  int ANS = INF;
  while (L < R) {
    if (L & 1) ANS = min(ANS, dat[L++]);
    if (R & 1) ANS = min(ANS, dat[--R]);
    L /= 2;
    R /= 2;
  }
  return ANS;
}

At the start of each loop iteration, the unprocessed interval corresponds exactly to the node indices \([L,R)\) at some depth.

If both nodes with indices \(2i,2i+1\) at that depth are included, we can replace them with their common parent \(i\). When grouping nodes into pairs of \(2\) in this way, an unpaired node may remain at either end.

  • If L is odd, the leftmost node L cannot be paired. Include its value in the answer and increase L by \(1\).
  • If R is odd, the rightmost node R-1 cannot be paired. Include its value in the answer and decrease R by \(1\).

After these steps, all remaining nodes form pairs of siblings. Replacing each pair with its parent gives the interval of node indices \([\lfloor L/2\rfloor,\lfloor R/2\rfloor)\) at the next level up.

Repeating this until L == R decomposes the queried interval into intervals represented by several nodes.

At most \(2\) node values are included in the answer at each level, and there are \(O(\log N)\) levels, so the time complexity is \(O(\log N)\).

Compared with the recursive implementation, this requires somewhat unusual index operations, but the code is shorter and also has an advantage in execution speed.

[2.5] Sample solutions

The following sample solutions combine the implementations above:

Implementing a segment tree is a standard learning topic for beginners, and many explanations are available online. Consult external resources as needed. For example, you may find my article

and its references useful.

[3] Using AtCoder Library

AtCoder Library provides a segment tree implementation, atcoder::segtree.

To use it, specify the type of the stored data, the operation op for combining information from \(2\) intervals, and its identity element e.

For this problem, use int for the data type, min for the operation, and a sufficiently large integer for the identity element. For example, define them as follows:

const int INF = 1'000'000'001;

int op(int a, int b) {
  return min(a, b);
}

int e() {
  return INF;
}

With these definitions, construct a segment tree from the initial sequence A:

atcoder::segtree<int, op, e> seg(A);

After construction, use the following operations:

  • seg.set(i,x): Change the element at position \(i\) to \(x\).
  • seg.prod(L,R): Find the minimum over the half-open interval \([L,R)\).

Both take \(O(\log N)\) time.

[4] Learning how to use segment trees

Besides range minimum queries, segment trees can handle various range queries, including range sums, range maximums, and matrix products.

The algebraic structure called a monoid is important for understanding which operations a segment tree can handle. AtCoder Library’s segtree is also based on monoids. See the following lecture for the definition of a monoid and some simple examples:

See the following lecture for ideas on designing more advanced monoids yourself and applying them to range queries:

You can also use this contest to learn about segment trees or to check your understanding.

posted:
last update: