Skip to content

Segment Tree Basics

Introduction

Segment Tree is a data structure commonly used in competitive programming to maintain interval information.

Segment Tree can perform operations such as single-point modification, interval modification, interval query (interval sum, interval maximum, interval minimum) in \(O(\log N)\) time complexity.

Basic Structure and Construction of Segment Tree

Process

Segment Tree recursively divides each interval of length not equal to \(1\) into left and right intervals, partitioning the entire segment into a tree structure, and obtains the information of the interval by merging the information of the left and right intervals. This data structure conveniently supports most interval operations.

Consider an array \(a=\{10,11,12,13,14\}\) of size \(5\). To convert it into a segment tree, we can do the following: Let the root node of the segment tree be numbered \(1\), and use array \(d\) to store our segment tree, where \(d_i\) stores the value of the node numbered \(i\) in the segment tree (here, the value maintained by each node is the sum of the interval represented by that node).

We first show the structure of this segment tree, as illustrated:

In the figure, the intervals marked in red within each node indicate the position interval in array \(a\) that the node governs. For example, the interval governed by \(d_1\) is \([1,5]\) (\(a_1,a_2, \cdots ,a_5\)), meaning the value stored in \(d_1\) is \(a_1+a_2+ \cdots +a_5\), and \(d_1=60\) indicates \(a_1+a_2+ \cdots +a_5=60\).

By observation, it is not difficult to see that the left child of \(d_i\) is \(d_{2\times i}\), and the right child of \(d_i\) is \(d_{2\times i+1}\). If \(d_i\) represents interval \([s,t]\) (i.e., \(d_i=a_s+a_{s+1}+ \cdots +a_t\)), then the left child of \(d_i\) represents interval \([ s, \frac{s+t}{2} ]\), and the right child of \(d_i\) represents interval \([ \frac{s+t}{2} +1,t ]\).

In implementation, we consider recursive construction. Let the current root node be \(p\). If the length of the interval governed by the root node is already \(1\), we can directly initialize the node based on the value at the corresponding position in array \(a\). Otherwise, we split the interval at the midpoint into two subintervals, recursively construct the tree for the left and right child nodes, and finally merge the information of the two child nodes.

Implementation

Here is the code implementation, with comments for understanding:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
void build(int s, int t, int p) {
  // Build segment tree for interval [s,t], current root number is p
  if (s == t) {
    d[p] = a[s];
    return;
  }
  int m = s + ((t - s) >> 1);
  // The precedence of shift operators is lower than addition/subtraction, so parentheses are added
  // If written as (s + t) >> 1, it might exceed int range
  build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
  // Recursively build tree for left and right intervals
  d[p] = d[p * 2] + d[(p * 2) + 1];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def build(s, t, p):
    # Build segment tree for interval [s,t], current root number is p
    if s == t:
        d[p] = a[s]
        return
    m = s + ((t - s) >> 1)
    # The precedence of shift operators is lower than addition/subtraction, so parentheses are added
    # If written as (s + t) >> 1, it might exceed int range
    build(s, m, p * 2)
    build(m + 1, t, p * 2 + 1)
    # Recursively build tree for left and right intervals
    d[p] = d[p * 2] + d[(p * 2) + 1]

Regarding segment tree space: If using heap storage (where \(2p\) is the left child of \(p\), and \(2p+1\) is the right child of \(p\)), if there are \(n\) leaf nodes, the maximum range of array d is \(2^{\left\lceil\log{n}\right\rceil+1}\).

Analysis: It is easy to know that the depth of the segment tree is \(\left\lceil\log{n}\right\rceil\). In heap storage, the number of leaf nodes (including unused leaf nodes) is \(2^{\left\lceil\log{n}\right\rceil}\). Since it is a complete binary tree, the total number of nodes is \(2^{\left\lceil\log{n}\right\rceil+1}-1\). Of course, if you prefer not to calculate, you can directly set the array length to \(4n\), because the maximum value of \(\frac{2^{\left\lceil\log{n}\right\rceil+1}-1}{n}\) is reached when \(n=2^{x}+1(x\in N_{+})\), where the number of nodes is \(2^{\left\lceil\log{n}\right\rceil+1}-1=2^{x+2}-1=4n-5\).

Heap storage has unused leaf nodes. Consider using a memory pool to manage segment tree nodes, obtaining a new node from the pool whenever needed. Considering from bottom up, every two bottom nodes merge into one upper node. Therefore, it can be proven similarly to Huffman tree that if there are \(n\) leaf nodes, such a segment tree has a total of \(2n-1\) nodes. Its space efficiency is better than heap storage and is possibly optimal.

Such a segment tree can be maintained from bottom up, refer to "The Power of Statistics - Zhang Kunwei".

Interval Query of Segment Tree

Process

Interval queries, such as finding the sum of interval \([l,r]\) (i.e., \(a_l+a_{l+1}+ \cdots +a_r\)), finding interval maximum/minimum, etc.

Still using the initial figure as an example, if we want to query the sum of interval \([1,5]\), we can directly get the value of \(d_1\) (\(60\)).

If the query interval is \([3,5]\), we cannot directly get the interval value. However, \([3,5]\) can be split into \([3,3]\) and \([4,5]\). The answer for this interval can be obtained by merging the answers of these two intervals.

Generally, if the query interval is \([l,r]\), it can be split into at most \(O(\log n)\) maximal intervals. Merging these intervals gives the answer for \([l,r]\).

Implementation

Here is the code implementation, with comments for understanding:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int getsum(int l, int r, int s, int t, int p) {
  // [l, r] is the query interval, [s, t] is the interval contained by the current node, p is the current node number
  if (l <= s && t <= r)
    return d[p];  // When the current interval is a subset of the query interval, directly return the sum of the current interval
  int m = s + ((t - s) >> 1), sum = 0;
  if (l <= m) sum += getsum(l, r, s, m, p * 2);
  // If the left child's interval [s, m] intersects with the query interval, recursively query the left child
  if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
  // If the right child's interval [m + 1, t] intersects with the query interval, recursively query the right child
  return sum;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def getsum(l, r, s, t, p):
    # [l, r] is the query interval, [s, t] is the interval contained by the current node, p is the current node number
    if l <= s and t <= r:
        return d[p]  # When the current interval is a subset of the query interval, directly return the sum of the current interval
    m = s + ((t - s) >> 1)
    sum = 0
    if l <= m:
        sum = sum + getsum(l, r, s, m, p * 2)
    # If the left child's interval [s, m] intersects with the query interval, recursively query the left child
    if r > m:
        sum = sum + getsum(l, r, m + 1, t, p * 2 + 1)
    # If the right child's interval [m + 1, t] intersects with the query interval, recursively query the right child
    return sum

Interval Modification and Lazy Propagation in Segment Tree

Process

If we want to modify interval \([l,r]\), traversing and modifying all nodes that are contained in interval \([l,r]\) would be unacceptably time-consuming. Here we introduce something called "lazy propagation".

Lazy propagation, simply put, delays changes to node information, thereby reducing potentially unnecessary operations. Each time a modification is performed, we mark the node to indicate that the corresponding interval was changed in some operation, but we do not update the information of the node's children. The actual modification is performed only the next time a node with a mark is accessed.

Still using the initial figure as an example, we will perform several operations of adding a value to each number in an interval. We now add a \(t_i\) to each node, representing the mark value carried by that node.

The initial situation is as follows (to save space, the interval governed by each node is not shown):

Now we want to add \(5\) to each number on \([3,5]\). Based on previous interval query experience, we quickly find two maximal intervals \([3,3]\) and \([4,5]\) (corresponding to nodes \(5\) and \(3\) in the segment tree, respectively).

We directly modify these two nodes and mark them:

We notice that although the information of node \(3\) is modified (since this interval governs two numbers, the value added to \(d_3\) is \(5 \times 2=10\)), its two child nodes are not yet updated and still retain the information before modification. However, don't worry. Although the modification hasn't been performed yet, when we need to query the information of these two child nodes, we will use the mark to modify their information, ensuring the query result remains accurate.

Next, we query the sum of numbers in interval \([4,4]\).

We recursively find interval \([4,5]\), but this interval is not our target interval, and there is still a mark on this interval. Now it's time to propagate the mark. We update the information of the two child intervals of this interval and clear the mark on this interval.

Now the values of nodes \(6\) and \(7\) become the latest values, and the query result is accurate.

Implementation

Next, we provide reference implementations for interval modification and query operations in the presence of marks.

Interval modification (adding a value to an interval):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// [l, r] is the modification interval, c is the change amount of the modified elements, [s, t] is the interval contained by the current node, p
// is the current node number
void update(int l, int r, int c, int s, int t, int p) {
  // When the current interval is a subset of the modification interval, directly modify the current node's value, then mark, end modification
  if (l <= s && t <= r) {
    d[p] += (t - s + 1) * c, b[p] += c;
    return;
  }
  int m = s + ((t - s) >> 1);
  if (b[p] && s != t) {
    // If the current node's lazy mark is non-empty, update the values and lazy marks of the current node's two child nodes
    d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
    b[p * 2] += b[p], b[p * 2 + 1] += b[p];  // Pass the mark down to child nodes
    b[p] = 0;                                // Clear the current node's mark
  }
  if (l <= m) update(l, r, c, s, m, p * 2);
  if (r > m) update(l, r, c, m + 1, t, p * 2 + 1);
  d[p] = d[p * 2] + d[p * 2 + 1];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def update(l, r, c, s, t, p):
    # [l, r] is the modification interval, c is the change amount of the modified elements, [s, t] is the interval contained by the current node, p
    # is the current node number
    if l <= s and t <= r:
        d[p] = d[p] + (t - s + 1) * c
        b[p] = b[p] + c
        return
    # When the current interval is a subset of the modification interval, directly modify the current node's value, then mark, end modification
    m = s + ((t - s) >> 1)
    if b[p] and s != t:
        # If the current node's lazy mark is non-empty, update the values and lazy marks of the current node's two child nodes
        d[p * 2] = d[p * 2] + b[p] * (m - s + 1)
        d[p * 2 + 1] = d[p * 2 + 1] + b[p] * (t - m)
        # Pass the mark down to child nodes
        b[p * 2] = b[p * 2] + b[p]
        b[p * 2 + 1] = b[p * 2 + 1] + b[p]
        # Clear the current node's mark
        b[p] = 0
    if l <= m:
        update(l, r, c, s, m, p * 2)
    if r > m:
        update(l, r, c, m + 1, t, p * 2 + 1)
    d[p] = d[p * 2] + d[p * 2 + 1]

Interval query (interval sum):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
int getsum(int l, int r, int s, int t, int p) {
  // [l, r] is the query interval, [s, t] is the interval contained by the current node, p is the current node number
  if (l <= s && t <= r) return d[p];
  // When the current interval is a subset of the query interval, directly return the sum of the current interval
  int m = s + ((t - s) >> 1);
  if (b[p]) {
    // If the current node's lazy mark is non-empty, update the values and lazy marks of the current node's two child nodes
    d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
    b[p * 2] += b[p], b[p * 2 + 1] += b[p];  // Pass the mark down to child nodes
    b[p] = 0;                                // Clear the current node's mark
  }
  int sum = 0;
  if (l <= m) sum = getsum(l, r, s, m, p * 2);
  if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
  return sum;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def getsum(l, r, s, t, p):
    # [l, r] is the query interval, [s, t] is the interval contained by the current node, p is the current node number
    if l <= s and t <= r:
        return d[p]
    # When the current interval is a subset of the query interval, directly return the sum of the current interval
    m = s + ((t - s) >> 1)
    if b[p]:
        # If the current node's lazy mark is non-empty, update the values and lazy marks of the current node's two child nodes
        d[p * 2] = d[p * 2] + b[p] * (m - s + 1)
        d[p * 2 + 1] = d[p * 2 + 1] + b[p] * (t - m)
        # Pass the mark down to child nodes
        b[p * 2] = b[p * 2] + b[p]
        b[p * 2 + 1] = b[p * 2 + 1] + b[p]
        # Clear the current node's mark
        b[p] = 0
    sum = 0
    if l <= m:
        sum = getsum(l, r, s, m, p * 2)
    if r > m:
        sum = sum + getsum(l, r, m + 1, t, p * 2 + 1)
    return sum

If you want to implement interval modification to a specific value rather than adding a value, the code is as follows:

 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
void update(int l, int r, int c, int s, int t, int p) {
  if (l <= s && t <= r) {
    d[p] = (t - s + 1) * c, b[p] = c, v[p] = 1;
    return;
  }
  int m = s + ((t - s) >> 1);
  // Additional array to store whether the value is modified
  if (v[p]) {
    d[p * 2] = b[p] * (m - s + 1), d[p * 2 + 1] = b[p] * (t - m);
    b[p * 2] = b[p * 2 + 1] = b[p];
    v[p * 2] = v[p * 2 + 1] = 1;
    v[p] = 0;
  }
  if (l <= m) update(l, r, c, s, m, p * 2);
  if (r > m) update(l, r, c, m + 1, t, p * 2 + 1);
  d[p] = d[p * 2] + d[p * 2 + 1];
}

int getsum(int l, int r, int s, int t, int p) {
  if (l <= s && t <= r) return d[p];
  int m = s + ((t - s) >> 1);
  if (v[p]) {
    d[p * 2] = b[p] * (m - s + 1), d[p * 2 + 1] = b[p] * (t - m);
    b[p * 2] = b[p * 2 + 1] = b[p];
    v[p * 2] = v[p * 2 + 1] = 1;
    v[p] = 0;
  }
  int sum = 0;
  if (l <= m) sum = getsum(l, r, s, m, p * 2);
  if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
  return sum;
}

 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
def update(l, r, c, s, t, p):
    if l <= s and t <= r:
        d[p] = (t - s + 1) * c
        b[p] = c
        v[p] = 1
        return
    m = s + ((t - s) >> 1)
    if v[p]:
        d[p * 2] = b[p] * (m - s + 1)
        d[p * 2 + 1] = b[p] * (t - m)
        b[p * 2] = b[p * 2 + 1] = b[p]
        v[p * 2] = v[p * 2 + 1] = 1
        v[p] = 0
    if l <= m:
        update(l, r, c, s, m, p * 2)
    if r > m:
        update(l, r, c, m + 1, t, p * 2 + 1)
    d[p] = d[p * 2] + d[p * 2 + 1]


def getsum(l, r, s, t, p):
    if l <= s and t <= r:
        return d[p]
    m = s + ((t - s) >> 1)
    if v[p]:
        d[p * 2] = b[p] * (m - s + 1)
        d[p * 2 + 1] = b[p] * (t - m)
        b[p * 2] = b[p * 2 + 1] = b[p]
        v[p * 2] = v[p * 2 + 1] = 1
        v[p] = 0
    sum = 0
    if l <= m:
        sum = getsum(l, r, s, m, p * 2)
    if r > m:
        sum = sum + getsum(l, r, m + 1, t, p * 2 + 1)
    return sum

Dynamic Segment Tree

As mentioned earlier, under heap storage, we need to allocate an array of size \(4n\) for the segment tree. To save space, we can avoid building the entire tree at once. Instead, we initially only create a root node representing the entire interval. When we need to access a subinterval, we then create the child node representing that interval. In this approach, we no longer use \(2p\) and \(2p+1\) to represent the children of node \(p\), but use \(\text{ls}\) and \(\text{rs}\) to record the child numbers. In summary, the core idea of dynamic segment tree is: nodes are created only when needed.

The time complexity of a single operation remains unchanged at \(O(\log n)\). Since each operation may create and access a completely new series of nodes, the number of nodes after \(m\) single-point operations is \(O(m\log n)\). At most, only \(2n-1\) nodes are needed, with no waste.

Single-point modification:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
// root represents the root node of the entire segment tree; cnt represents the current number of nodes
int n, cnt, root;
int sum[n * 2], ls[n * 2], rs[n * 2];

// Usage: update(root, 1, n, x, f); where x is the number of the node to be modified
void update(int& p, int s, int t, int x, int f) {  // Pass by reference
  if (!p) p = ++cnt;  // When the node is empty, create a new node
  if (s == t) {
    sum[p] += f;
    return;
  }
  int m = s + ((t - s) >> 1);
  if (x <= m)
    update(ls[p], s, m, x, f);
  else
    update(rs[p], m + 1, t, x, f);
  sum[p] = sum[ls[p]] + sum[rs[p]];  // pushup
}

Interval query:

1
2
3
4
5
6
7
8
9
// Usage: query(root, 1, n, l, r);
int query(int p, int s, int t, int l, int r) {
  if (!p) return 0;  // If the node is empty, return 0
  if (s >= l && t <= r) return sum[p];
  int m = s + ((t - s) >> 1), ans = 0;
  if (l <= m) ans += query(ls[p], s, m, l, r);
  if (r > m) ans += query(rs[p], m + 1, t, l, r);
  return ans;
}

Interval modification is similar, but when propagating marks, be careful to create a new child if one is missing. Alternatively, use the technique of permanent marks.

Some Optimizations

Here are some optimizations for segment trees:

  • At leaf nodes, there is no need to propagate lazy marks, so lazy marks can be not propagated to leaf nodes.

  • Propagating lazy marks can be written as a dedicated function pushdown, and updating the current node from child nodes can be written as a dedicated function maintain (or symmetrically pushup), reducing code complexity.

  • Permanent marks: If it is certain that lazy marks will not overflow (i.e., exceed the maximum range representable by the data type) during the process, then marks can be made permanent. Permanent marks avoid propagating lazy marks; only when querying, the effect of the mark is added to the answer, thereby reducing constant factors. The specific handling depends on the problem characteristics and must be written in conjunction with the problem. This is also a technique used in segment tree of segment trees and persistent data structures.

C++ Templates

SegTreeLazyRangeAdd Segment Tree Template for Interval Addition/Sum 
 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
#include <bits/stdc++.h>
using namespace std;

template <typename T>
class SegTreeLazyRangeAdd {
  vector<T> tree, lazy;
  vector<T> *arr;
  int n, root, n4, end;

  void maintain(int cl, int cr, int p) {
    int cm = cl + (cr - cl) / 2;
    if (cl != cr && lazy[p]) {
      lazy[p * 2] += lazy[p];
      lazy[p * 2 + 1] += lazy[p];
      tree[p * 2] += lazy[p] * (cm - cl + 1);
      tree[p * 2 + 1] += lazy[p] * (cr - cm);
      lazy[p] = 0;
    }
  }

  T range_sum(int l, int r, int cl, int cr, int p) {
    if (l <= cl && cr <= r) return tree[p];
    int m = cl + (cr - cl) / 2;
    T sum = 0;
    maintain(cl, cr, p);
    if (l <= m) sum += range_sum(l, r, cl, m, p * 2);
    if (r > m) sum += range_sum(l, r, m + 1, cr, p * 2 + 1);
    return sum;
  }

  void range_add(int l, int r, T val, int cl, int cr, int p) {
    if (l <= cl && cr <= r) {
      lazy[p] += val;
      tree[p] += (cr - cl + 1) * val;
      return;
    }
    int m = cl + (cr - cl) / 2;
    maintain(cl, cr, p);
    if (l <= m) range_add(l, r, val, cl, m, p * 2);
    if (r > m) range_add(l, r, val, m + 1, cr, p * 2 + 1);
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
  }

  void build(int s, int t, int p) {
    if (s == t) {
      tree[p] = (*arr)[s];
      return;
    }
    int m = s + (t - s) / 2;
    build(s, m, p * 2);
    build(m + 1, t, p * 2 + 1);
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
  }

 public:
  explicit SegTreeLazyRangeAdd<T>(vector<T> v) {
    n = v.size();
    n4 = n * 4;
    tree = vector<T>(n4, 0);
    lazy = vector<T>(n4, 0);
    arr = &v;
    end = n - 1;
    root = 1;
    build(0, end, 1);
    arr = nullptr;
  }

  void show(int p, int depth = 0) {
    if (p > n4 || tree[p] == 0) return;
    show(p * 2, depth + 1);
    for (int i = 0; i < depth; ++i) putchar('\t');
    printf("%d:%d\n", tree[p], lazy[p]);
    show(p * 2 + 1, depth + 1);
  }

  T range_sum(int l, int r) { return range_sum(l, r, 0, end, root); }

  void range_add(int l, int r, T val) { range_add(l, r, val, 0, end, root); }
};
SegTreeLazyRangeSet Segment Tree Template for Interval Modification/Sum 
 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
#include <bits/stdc++.h>
using namespace std;

template <typename T>
class SegTreeLazyRangeSet {
  vector<T> tree, lazy;
  vector<T> *arr;
  vector<bool> ifLazy;
  int n, root, n4, end;

  void maintain(int cl, int cr, int p) {
    int cm = cl + (cr - cl) / 2;
    if (cl != cr && ifLazy[p]) {
      lazy[p * 2] = lazy[p], ifLazy[p * 2] = 1;
      lazy[p * 2 + 1] = lazy[p], ifLazy[p * 2 + 1] = 1;
      tree[p * 2] = lazy[p] * (cm - cl + 1);
      tree[p * 2 + 1] = lazy[p] * (cr - cm);
      lazy[p] = 0;
      ifLazy[p] = 0;
    }
  }

  T range_sum(int l, int r, int cl, int cr, int p) {
    if (l <= cl && cr <= r) return tree[p];
    int m = cl + (cr - cl) / 2;
    T sum = 0;
    maintain(cl, cr, p);
    if (l <= m) sum += range_sum(l, r, cl, m, p * 2);
    if (r > m) sum += range_sum(l, r, m + 1, cr, p * 2 + 1);
    return sum;
  }

  void range_set(int l, int r, T val, int cl, int cr, int p) {
    if (l <= cl && cr <= r) {
      lazy[p] = val;
      ifLazy[p] = 1;
      tree[p] = (cr - cl + 1) * val;
      return;
    }
    int m = cl + (cr - cl) / 2;
    maintain(cl, cr, p);
    if (l <= m) range_set(l, r, val, cl, m, p * 2);
    if (r > m) range_set(l, r, val, m + 1, cr, p * 2 + 1);
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
  }

  void build(int s, int t, int p) {
    if (s == t) {
      tree[p] = (*arr)[s];
      return;
    }
    int m = s + (t - s) / 2;
    build(s, m, p * 2);
    build(m + 1, t, p * 2 + 1);
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
  }

 public:
  explicit SegTreeLazyRangeSet<T>(vector<T> v) {
    n = v.size();
    n4 = n * 4;
    tree = vector<T>(n4, 0);
    lazy = vector<T>(n4, 0);
    ifLazy = vector<bool>(n4, 0);
    arr = &v;
    end = n - 1;
    root = 1;
    build(0, end, 1);
    arr = nullptr;
  }

  void show(int p, int depth = 0) {
    if (p > n4 || tree[p] == 0) return;
    show(p * 2, depth + 1);
    for (int i = 0; i < depth; ++i) putchar('\t');
    printf("%d:%d\n", tree[p], lazy[p]);
    show(p * 2 + 1, depth + 1);
  }

  T range_sum(int l, int r) { return range_sum(l, r, 0, end, root); }

  void range_set(int l, int r, T val) { range_set(l, r, val, 0, end, root); }
};

Examples

luogu P3372【Template】Segment Tree 1

Given a sequence, you need to perform two types of operations:

  • Add \(k\) to every number in a certain interval.

  • Find the sum of every number in a certain interval.

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
#include <iostream>
using LL = long long;
LL n, a[100005], d[270000], b[270000];

void build(LL l, LL r, LL p) {  // l: interval left endpoint r: interval right endpoint p: node index
  if (l == r) {
    d[p] = a[l];  // assign value to the node
    return;
  }
  LL m = l + ((r - l) >> 1);
  build(l, m, p << 1), build(m + 1, r, (p << 1) | 1);  // build left and right subtrees respectively
  d[p] = d[p << 1] + d[(p << 1) | 1];
}

void update(LL l, LL r, LL c, LL s, LL t, LL p) {
  if (l <= s && t <= r) {
    d[p] += (t - s + 1) * c, b[p] += c;  // if the interval is fully covered, directly compute the answer
    return;
  }
  LL m = s + ((t - s) >> 1);
  if (b[p])
    d[p << 1] += b[p] * (m - s + 1), d[(p << 1) | 1] += b[p] * (t - m),
        b[p << 1] += b[p], b[(p << 1) | 1] += b[p];
  b[p] = 0;
  if (l <= m)
    update(l, r, c, s, m, p << 1);  // this line and the next line update nodes p*2 and p*2+1
  if (r > m) update(l, r, c, m + 1, t, (p << 1) | 1);
  d[p] = d[p << 1] + d[(p << 1) | 1];  // compute the interval sum for this node
}

LL getsum(LL l, LL r, LL s, LL t, LL p) {
  if (l <= s && t <= r) return d[p];
  LL m = s + ((t - s) >> 1);
  if (b[p])
    d[p << 1] += b[p] * (m - s + 1), d[(p << 1) | 1] += b[p] * (t - m),
        b[p << 1] += b[p], b[(p << 1) | 1] += b[p];
  b[p] = 0;
  LL sum = 0;
  if (l <= m)
    sum =
        getsum(l, r, s, m, p << 1);  // this line and the next line update answers for p*2 and p*2+1
  if (r > m) sum += getsum(l, r, m + 1, t, (p << 1) | 1);
  return sum;
}

int main() {
  std::ios::sync_with_stdio(false);
  LL q, i1, i2, i3, i4;
  std::cin >> n >> q;
  for (LL i = 1; i <= n; i++) std::cin >> a[i];
  build(1, n, 1);
  while (q--) {
    std::cin >> i1 >> i2 >> i3;
    if (i1 == 2)
      std::cout << getsum(i2, i3, 1, n, 1) << std::endl;  // directly call the operation function
    else
      std::cin >> i4, update(i2, i3, i4, 1, n, 1);
  }
  return 0;
}
luogu P3373【Template】Segment Tree 2

Given a sequence, you need to perform three types of operations:

  • Multiply every number in a certain interval by \(x\).

  • Add \(x\) to every number in a certain interval.

  • Find the sum of every number in a certain interval.

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>
using ll = long long;

int n, m;
ll mod;
ll a[100005], sum[400005], mul[400005], laz[400005];

void up(int i) { sum[i] = (sum[(i << 1)] + sum[(i << 1) | 1]) % mod; }

void pd(int i, int s, int t) {
  int l = (i << 1), r = (i << 1) | 1, mid = (s + t) >> 1;
  if (mul[i] != 1) {  // Lazy tag propagation, two lazy tags
    mul[l] *= mul[i];
    mul[l] %= mod;
    mul[r] *= mul[i];
    mul[r] %= mod;
    laz[l] *= mul[i];
    laz[l] %= mod;
    laz[r] *= mul[i];
    laz[r] %= mod;
    sum[l] *= mul[i];
    sum[l] %= mod;
    sum[r] *= mul[i];
    sum[r] %= mod;
    mul[i] = 1;
  }
  if (laz[i]) {  // Lazy tag propagation
    sum[l] += laz[i] * (mid - s + 1);
    sum[l] %= mod;
    sum[r] += laz[i] * (t - mid);
    sum[r] %= mod;
    laz[l] += laz[i];
    laz[l] %= mod;
    laz[r] += laz[i];
    laz[r] %= mod;
    laz[i] = 0;
  }
  return;
}

void build(int s, int t, int i) {
  mul[i] = 1;
  if (s == t) {
    sum[i] = a[s];
    return;
  }
  int mid = s + ((t - s) >> 1);
  build(s, mid, i << 1);  // Build the tree
  build(mid + 1, t, (i << 1) | 1);
  up(i);
}

void chen(int l, int r, int s, int t, int i, ll z) {
  int mid = s + ((t - s) >> 1);
  if (l <= s && t <= r) {
    mul[i] *= z;
    mul[i] %= mod;  // This is modulo
    laz[i] *= z;
    laz[i] %= mod;  // This is modulo
    sum[i] *= z;
    sum[i] %= mod;  // This is modulo
    return;
  }
  pd(i, s, t);
  if (mid >= l) chen(l, r, s, mid, (i << 1), z);
  if (mid + 1 <= r) chen(l, r, mid + 1, t, (i << 1) | 1, z);
  up(i);
}

void add(int l, int r, int s, int t, int i, ll z) {
  int mid = s + ((t - s) >> 1);
  if (l <= s && t <= r) {
    sum[i] += z * (t - s + 1);
    sum[i] %= mod;  // This is modulo
    laz[i] += z;
    laz[i] %= mod;  // This is modulo
    return;
  }
  pd(i, s, t);
  if (mid >= l) add(l, r, s, mid, (i << 1), z);
  if (mid + 1 <= r) add(l, r, mid + 1, t, (i << 1) | 1, z);
  up(i);
}

ll getans(int l, int r, int s, int t,
          int i) {  // Get the answer, you can refer to the lazy tags above for understanding
  int mid = s + ((t - s) >> 1);
  ll tot = 0;
  if (l <= s && t <= r) return sum[i];
  pd(i, s, t);
  if (mid >= l) tot += getans(l, r, s, mid, (i << 1));
  tot %= mod;
  if (mid + 1 <= r) tot += getans(l, r, mid + 1, t, (i << 1) | 1);
  return tot % mod;
}

using std::cin;
using std::cout;

int main() {  // Read input
  cin.tie(nullptr)->sync_with_stdio(false);
  int i, j, x, y, bh;
  ll z;
  cin >> n >> m >> mod;
  for (i = 1; i <= n; i++) cin >> a[i];
  build(1, n, 1);  // Build the tree
  for (i = 1; i <= m; i++) {
    cin >> bh;
    if (bh == 1) {
      cin >> x >> y >> z;
      chen(x, y, 1, n, 1, z);
    } else if (bh == 2) {
      cin >> x >> y >> z;
      add(x, y, 1, n, 1, z);
    } else if (bh == 3) {
      cin >> x >> y;
      cout << getans(x, y, 1, n, 1) << '\n';
    }
  }
  return 0;
}
HihoCoder 1078 Segment Tree Interval Modification

Suppose there are \(N\) products placed on a shelf from left to right, numbered from \(1\) to \(N\), where the price of product \(i\) is \(Pi\). Each operation by Little Hi is one of two possibilities. The first is price modification: Little Hi gives an interval \([L, R]\) and a new price \(\textit{NewP}\), and the prices of all products numbered in this interval become \(\textit{NewP}\). The second operation is query: Little Hi gives an interval \([L, R]\), and Little Ho needs to calculate the total price of all products numbered in this interval and tell Little Hi.

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
#include <iostream>

int n, a[100005], d[270000], b[270000];

void build(int l, int r, int p) {  // Build the segment tree
  if (l == r) {
    d[p] = a[l];
    return;
  }
  int m = l + ((r - l) >> 1);
  build(l, m, p << 1), build(m + 1, r, (p << 1) | 1);
  d[p] = d[p << 1] + d[(p << 1) | 1];
}

void update(int l, int r, int c, int s, int t,
            int p) {  // Update, can refer to the previous two examples
  if (l <= s && t <= r) {
    d[p] = (t - s + 1) * c, b[p] = c;
    return;
  }
  int m = s + ((t - s) >> 1);
  if (b[p]) {
    d[p << 1] = b[p] * (m - s + 1), d[(p << 1) | 1] = b[p] * (t - m);
    b[p << 1] = b[(p << 1) | 1] = b[p];
    b[p] = 0;
  }
  if (l <= m) update(l, r, c, s, m, p << 1);
  if (r > m) update(l, r, c, m + 1, t, (p << 1) | 1);
  d[p] = d[p << 1] + d[(p << 1) | 1];
}

int getsum(int l, int r, int s, int t, int p) {  // Get the answer, same as before
  if (l <= s && t <= r) return d[p];
  int m = s + ((t - s) >> 1);
  if (b[p]) {
    d[p << 1] = b[p] * (m - s + 1), d[(p << 1) | 1] = b[p] * (t - m);
    b[p << 1] = b[(p << 1) | 1] = b[p];
    b[p] = 0;
  }
  int sum = 0;
  if (l <= m) sum = getsum(l, r, s, m, p << 1);
  if (r > m) sum += getsum(l, r, m + 1, t, (p << 1) | 1);
  return sum;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin >> n;
  for (int i = 1; i <= n; i++) std::cin >> a[i];
  build(1, n, 1);
  int q, i1, i2, i3, i4;
  std::cin >> q;
  while (q--) {
    std::cin >> i1 >> i2 >> i3;
    if (i1 == 0)
      std::cout << getsum(i2, i3, 1, n, 1) << std::endl;
    else
      std::cin >> i4, update(i2, i3, i4, 1, n, 1);
  }
  return 0;
}
2018 Multi-University Training Contest 5 Problem G. Glad You Came
Solution Idea

Maintain the permanent mark for each interval, and finally run a DFS on the segment tree to collect results. Note to add a pruning optimization when marking, otherwise it will TLE.

Extensions

Segment trees are widely applied, common extensions and variants include:

For details, please refer to the relevant pages.

Application: Segment Tree Optimized Graph Construction

During graph construction and edge addition, we sometimes encounter problems where a point connects to a continuous interval of points, or a continuous interval connects to a point. If we connect them one by one, once the number of points increases, the complexity explodes. Here we can use the interval property of segment trees to optimize our graph construction.

Below is a segment tree.

Each node represents an interval. Suppose we want to connect edges to interval \([2, 4]\).

In some problems, there is also the case where an interval connects to a point. Then we simply reverse all directed edges in the first figure above. The tree above is called the "in-tree", and the one below is called the "out-tree".

Legacy

Problem summary: There are \(n\) points and \(q\) operations. Each operation is one of the following three types:

  • Operation 1: Add a directed edge \(u \rightarrow v\) with weight \(w\).
  • Operation 2: For all \(i \in [l,r]\), add a directed edge \(u \rightarrow i\) with weight \(w\).
  • Operation 3: For all \(i \in [l,r]\), add a directed edge \(i \rightarrow u\) with weight \(w\).

Find the shortest path from point \(s\) to other points.

\(1 \le n,q \le 10^5, 1 \le w \le 10^9\).

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
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
#include <bitset>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
using ll = long long;

constexpr int N = 1e5 + 5;

using pil = pair<int, ll>;
using pli = pair<ll, int>;

int n, q, s, tot, rt1, rt2;
int pos[N];
ll dis[N << 3];
vector<pil> e[N << 3];
bitset<(N << 3)> vis;

struct seg {
  int l, r, lson, rson;
} t[N << 3];

int ls(int u) {  // Left child
  return t[u].lson;
}

int rs(int u) {  // Right child
  return t[u].rson;
}

void build(int &u, int l, int r) {  // Dynamically build the in-tree
  u = ++tot;
  t[u] = seg{l, r};
  if (l == r) {
    pos[l] = u;
    return;
  }
  int mid = (l + r) >> 1;
  build(t[u].lson, l, mid);
  build(t[u].rson, mid + 1, r);
  e[u].emplace_back(ls(u), 0);
  e[u].emplace_back(rs(u), 0);
}

void build2(int &u, int l, int r) {  // Dynamically build the out-tree
  if (l == r) {
    u = pos[l];
    return;
  }
  u = ++tot;
  t[u] = seg{l, r};
  int mid = (l + r) >> 1;
  build2(t[u].lson, l, mid);
  build2(t[u].rson, mid + 1, r);
  e[ls(u)].emplace_back(u, 0);
  e[rs(u)].emplace_back(u, 0);
}

void add1(int u, int lr, int rr, int v, ll w) {  // Connect point to interval
  if (lr <= t[u].l && t[u].r <= rr) {
    e[v].emplace_back(u, w);
    return;
  }
  int mid = (t[u].l + t[u].r) >> 1;
  if (lr <= mid) {
    add1(ls(u), lr, rr, v, w);
  }
  if (rr > mid) {
    add1(rs(u), lr, rr, v, w);
  }
}

void add2(int u, int lr, int rr, int v, ll w) {  // Connect interval to point
  if (lr <= t[u].l && t[u].r <= rr) {
    e[u].emplace_back(v, w);
    return;
  }
  int mid = (t[u].l + t[u].r) >> 1;
  if (lr <= mid) {
    add2(ls(u), lr, rr, v, w);
  }
  if (rr > mid) {
    add2(rs(u), lr, rr, v, w);
  }
}

void dij(int S) {
  priority_queue<pli, vector<pli>, greater<pli>> q;
  int tot = (n << 2);
  for (int i = 1; i <= tot; ++i) {
    dis[i] = 1e18;
  }
  dis[S] = 0;
  q.emplace(dis[S], S);
  while (!q.empty()) {
    pli fr = q.top();
    q.pop();
    int u = fr.second;
    if (vis[u]) continue;
    for (pil it : e[u]) {
      int v = it.first;
      ll w = it.second;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.emplace(dis[v], v);
      }
    }
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> q >> s;
  build(rt1, 1, n);
  build2(rt2, 1, n);
  for (int i = 1, op, u; i <= q; ++i) {
    cin >> op >> u;
    if (op == 1) {
      int v;
      ll w;
      cin >> v >> w;
      e[pos[u]].emplace_back(pos[v], w);
    } else if (op == 2) {
      int l, r;
      ll w;
      cin >> l >> r >> w;
      add1(rt1, l, r, pos[u], w);
    } else {
      int l, r;
      ll w;
      cin >> l >> r >> w;
      add2(rt2, l, r, pos[u], w);
    }
  }
  dij(pos[s]);
  for (int i = 1; i <= n; ++i) {
    if (dis[pos[i]] == 1e18) {
      cout << "-1 ";
    } else {
      cout << dis[pos[i]] << ' ';
    }
  }
  return 0;
}

Practice Problems

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