Segment Tree Basics

Introduction

Segment trees are commonly used in algorithm contests to maintain range information.

Segment trees support point updates, range updates, and range queries (range sums, range maxima, and range minima) in $O(\log N)$ time.

Basic Structure and Building a Segment Tree

Process

A segment tree recursively divides every interval of length greater than $1$ into a left interval and a right interval, turning the entire segment into a tree structure. The information for an interval is obtained by merging the information of its two subintervals. This data structure makes most range operations convenient.

Consider an array of size $5$, $a=\{10,11,12,13,14\}$. To turn it into a segment tree, let the root of the segment tree have index $1$, and use an array $d$ to store the segment tree. $d_i$ stores its value of this node with index $i$ in the segment tree; here, each node stores the sum of this interval it represents.

We first show the shape of this segment tree, as in the figure:

The intervals marked in red in the figure are the position intervals of the $a$ array managed by each node. For example, this interval managed by $d_1$ is $[1,5]$ (that is, $a_1,a_2, \cdots ,a_5$), so its value stored in $d_1$ is $a_1+a_2+ \cdots +a_5$. The statement $d_1=60$ means $a_1+a_2+ \cdots +a_5=60$.

It is easy 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 this interval $[s,t]$ (that is, $d_i=a_s+a_{s+1}+ \cdots +a_t$), then the left child of $d_i$ represents $[ s, \frac{s+t}{2} ]$, and the right child of $d_i$ represents $[ \frac{s+t}{2} +1,t ]$.

In the implementation, we build the tree recursively. Let the current root be node $p$. If this interval managed by the root already has length $1$, initialize this node directly from the corresponding value in the $a$ array. Otherwise, split this interval at its midpoint into two subintervals, recursively build the left and right children, and finally merge the information from the two children.

Implementation

Here is a code implementation; the comments may help explain it:

C++

void build(int s, int t, int p) {
  // Build a segment tree for [s,t]; p is the index of the current root
  if (s == t) {
    d[p] = a[s];
    return;
  }
  int m = s + ((t - s) >> 1);
  // The shift operator has lower precedence than addition and subtraction, so add parentheses
  // Writing (s + t) >> 1 may overflow the int range
  build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
  // Recursively build the tree for the left and right intervals
  d[p] = d[p * 2] + d[(p * 2) + 1];
}

Python

def build(s, t, p):
    # Build a segment tree for [s,t]; p is the index of the current root
    if s == t:
        d[p] = a[s]
        return
    m = s + ((t - s) >> 1)
    # The shift operator has lower precedence than addition and subtraction, so add parentheses
    # Writing (s + t) >> 1 may overflow the int range
    build(s, m, p * 2)
    build(m + 1, t, p * 2 + 1)
    # Recursively build the tree for the left and right intervals
    d[p] = d[p * 2] + d[(p * 2) + 1]

Regarding the space used by a segment tree: with heap-style storage ($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 the array d is $2^{\left\lceil\log{n}\right\rceil+1}$.

Analysis: the depth of a segment tree is clearly $\left\lceil\log{n}\right\rceil$. Under heap-style storage, the number of leaf nodes (including unused leaves) is $2^{\left\lceil\log{n}\right\rceil}$, and because the tree is a complete binary tree, its total number of nodes is $2^{\left\lceil\log{n}\right\rceil+1}-1$. If you do not want to calculate this, you can simply set the array length to $4n$, because the maximum of $\frac{2^{\left\lceil\log{n}\right\rceil+1}-1}{n}$ is attained when $n=2^{x}+1(x\in N_{+})$. In that case, this node count is $2^{\left\lceil\log{n}\right\rceil+1}-1=2^{x+2}-1=4n-5$.

Heap-style storage has unused leaf nodes, so a memory pool can be used to manage segment-tree nodes: obtain a node from the pool whenever a new node is needed. Working upward from the bottom, every two nodes at the lowest level must merge into one node at the next level. Thus, by an argument similar to the one for a Huffman tree, a segment tree with $n$ leaf nodes has $2n-1$ nodes in total. Its space efficiency is better than heap-style storage and is also optimal.

Such a segment tree can be maintained from the bottom up; see Statistical Power - Zhang Kunwei.

Range Queries on a Segment Tree

Process

A range query may ask for the sum of an interval $[l,r]$ (that is, $a_l+a_{l+1}+ \cdots +a_r$), or for its maximum or minimum.

Using the original figure as an example, to query the sum of $[1,5]$, simply obtain its value of $d_1$, namely $60$.

If this query interval is $[3,5]$, its value cannot be obtained directly. However, $[3,5]$ can be split into $[3,3]$ and $[4,5]$, and the answer for this interval can be obtained by merging the answers for these two intervals.

In general, if this query interval is $[l,r]$, it can be split into at most $O(\log n)$ maximal intervals, whose answers can then be merged to obtain the answer for $[l,r]$.

Implementation

Here is a code implementation; the comments may help explain it:

C++

int getsum(int l, int r, int s, int t, int p) {
  // [l, r] is this query interval, [s, t] is this interval contained by the current node, and p is the current node's index
  if (l <= s && t <= r)
    return d[p];  // Return the sum of the current interval directly when it is contained in this query interval
  int m = s + ((t - s) >> 1), sum = 0;
  if (l <= m) sum += getsum(l, r, s, m, p * 2);
  // If this interval [s, m] represented by the left child intersects this query interval, recursively query the left child
  if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
  // If this interval [m + 1, t] represented by the right child intersects this query interval, recursively query the right child
  return sum;
}

Python

def getsum(l, r, s, t, p):
    # [l, r] is this query interval, [s, t] is this interval contained by the current node, and p is the current node's index
    if l <= s and t <= r:
        return d[p]  # Return the sum of the current interval directly when it is contained in this query interval
    m = s + ((t - s) >> 1)
    sum = 0
    if l <= m:
        sum = sum + getsum(l, r, s, m, p * 2)
    # If this interval [s, m] represented by the left child intersects this query interval, recursively query the left child
    if r > m:
        sum = sum + getsum(l, r, m + 1, t, p * 2 + 1)
    # If this interval [m + 1, t] represented by the right child intersects this query interval, recursively query the right child
    return sum

Range Updates and Lazy Propagation in a Segment Tree

Process

If we need to modify an interval $[l,r]$ by visiting and modifying every node contained in $[l,r]$, the time complexity is unacceptable. We therefore introduce lazy tags.

In simple terms, a lazy tag delays changes to node information, reducing potentially unnecessary operations. During each update, we attach a tag to indicate that this interval represented by this node was changed by an operation, but do not update the information of its children. The actual modification is performed only when a tagged node is visited later.

Again using the original figure, suppose we perform several operations that add a value to every number in an interval. We now add a $t_i$ to every node to represent its value of the tag carried by that node.

The initial state is as follows (this intervals managed by individual nodes are omitted to save space):

Now, for $[3,5]$, add $5$ to every number. Based on the range-query discussion above, we quickly find the two maximal intervals $[3,3]$ and $[4,5]$ (corresponding to nodes $5$ and $3$ in the segment tree, respectively).

We update these two nodes directly and attach tags to them:

We can see that the information in node $3$ has been updated (because its interval contains two numbers, the amount added to $d_3$ is $5 \times 2=10$), but its two children have not yet been updated and still retain their old information. There is no need to worry: although the update has not yet reached them, when we query the information of these two children, we use the tag to update their information, so this query result remains correct.

Next, query the sum of the numbers in this interval $[4,4]$.

Following the recursion, we find this interval $[4,5]$. It is not our target interval, and it still has a tag. This is when the tag must be pushed down. Update the information of its two child intervals and clear the tag on this interval.

The values of nodes $6$ and $7$ are now up to date, and this query result is also correct.

Implementation

We next give reference implementations of range updates and queries in the presence of tags.

Range update (add a value to an interval):

C++

// [l, r] is the update interval, c is the change applied to each element, [s, t] is this interval contained by the current node, and p
// is the current node's index
void update(int l, int r, int c, int s, int t, int p) {
  // When the current interval is contained in the update interval, modify the current node's value directly, attach a tag, and finish the update
  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 has a nonempty lazy tag, update its values and lazy tags of its two children
    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];  // Push the tag down to the children
    b[p] = 0;                                // Clear the current node's tag
  }
  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];
}

Python

def update(l, r, c, s, t, p):
    # [l, r] is the update interval, c is the change applied to each element, [s, t] is this interval contained by the current node, and p
    # is the current node's index
    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 contained in the update interval, modify the current node's value directly, attach a tag, and finish the update
    m = s + ((t - s) >> 1)
    if b[p] and s != t:
        # If the current node has a nonempty lazy tag, update its values and lazy tags of its two children
        d[p * 2] = d[p * 2] + b[p] * (m - s + 1)
        d[p * 2 + 1] = d[p * 2 + 1] + b[p] * (t - m)
        # Push the tag down to the children
        b[p * 2] = b[p * 2] + b[p]
        b[p * 2 + 1] = b[p * 2 + 1] + b[p]
        # Clear the current node's tag
        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]

Range query (range sum):

C++

int getsum(int l, int r, int s, int t, int p) {
  // [l, r] is this query interval, [s, t] is this interval contained by the current node, and p is the current node's index
  if (l <= s && t <= r) return d[p];
  // Return the sum of the current interval directly when it is contained in this query interval
  int m = s + ((t - s) >> 1);
  if (b[p]) {
    // If the current node has a nonempty lazy tag, update its values and lazy tags of its two children
    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];  // Push the tag down to the children
    b[p] = 0;                                // Clear the current node's tag
  }
  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;
}

Python

def getsum(l, r, s, t, p):
    # [l, r] is this query interval, [s, t] is this interval contained by the current node, and p is the current node's index
    if l <= s and t <= r:
        return d[p]
    # Return the sum of the current interval directly when it is contained in this query interval
    m = s + ((t - s) >> 1)
    if b[p]:
        # If the current node has a nonempty lazy tag, update its values and lazy tags of its two children
        d[p * 2] = d[p * 2] + b[p] * (m - s + 1)
        d[p * 2 + 1] = d[p * 2 + 1] + b[p] * (t - m)
        # Push the tag down to the children
        b[p * 2] = b[p * 2] + b[p]
        b[p * 2 + 1] = b[p * 2 + 1] + b[p]
        # Clear the current node's tag
        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 a range update that assigns one value rather than adding a value, use the following code:

C++

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);
  // An auxiliary array stores whether an assignment has been made
  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;
}

Python

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 Trees

As noted above, heap-style storage requires an array of size $4n$ for a segment tree. To save space, we can avoid building the whole tree at once and initially create only a root node representing the entire interval. A child node representing a subinterval is created only when that subinterval needs to be accessed. We no longer use $2p$ and $2p+1$ as the children of node $p$; instead, we use $\text{ls}$ and $\text{rs}$ to store the child indices. In short, the central idea of a dynamic segment tree is: a node is created only when it is needed.

The time complexity of a single operation remains $O(\log n)$. Since each operation may create and visit an entirely new sequence of nodes, the number of nodes after $m$ point operations is $O(m\log n)$. At most $2n-1$ nodes are needed, with no waste.

Point update:

// root is the root of the entire segment tree; cnt is 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); x is the index of this node to update
void update(int& p, int s, int t, int x, int f) {  // Pass by reference
  if (!p) p = ++cnt;  // Create a new node when this node is empty
  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
}

Range query:

// Usage: query(root, 1, n, l, r);
int query(int p, int s, int t, int l, int r) {
  if (!p) return 0;  // Return 0 when this node is empty
  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;
}

Range updates are handled similarly, but when pushing down a tag, if a child is missing, create it directly. Alternatively, use the technique of making tags persistent.

Some Optimizations

Here is a summary of several segment-tree optimizations:

• At a leaf node, there is no need to push down a lazy tag, so lazy tags do not need to be propagated to leaf nodes.

• Lazy propagation can be written as a dedicated function pushdown, and updating the current node from its children can likewise be written as a dedicated function maintain (or symmetrically pushup), reducing the difficulty of writing the code.

• Tag persistence: if you are sure that a lazy tag will not overflow during this process (that is, exceed the maximum value representable by its data type), the tag can be made persistent. Persistent tags avoid pushing lazy tags down; when answering a query, simply add the tag's effect to the answer, reducing the program constant. The exact handling depends on the problem's properties and should be implemented accordingly. This is also a technique used in segment-tree-over-segment-tree and persistent data structures.

C++ Templates

#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); }
};

#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

#include <iostream>
using LL = long long;
LL n, a[100005], d[270000], b[270000];

void build(LL l, LL r, LL p) {  // l: left endpoint of this interval; r: right endpoint; p: node index
  if (l == r) {
    d[p] = a[l];  // Assign a value to this node
    return;
  }
  LL m = l + ((r - l) >> 1);
  build(l, m, p << 1), build(m + 1, r, (p << 1) | 1);  // Build the two subtrees
  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 this interval is contained, obtain the answer directly
    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 update the p*2 and p*2+1 nodes
  if (r > m) update(l, r, c, m + 1, t, (p << 1) | 1);
  d[p] = d[p << 1] + d[(p << 1) | 1];  // Compute the sum of this node's interval
}

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 update the 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;  // Call an operation function directly
    else
      std::cin >> i4, update(i2, i3, i4, 1, n, 1);
  }
  return 0;
}

#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) {  // Propagate the 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]) {  // Propagate the lazy tag
    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;  // Take the modulus here
    laz[i] *= z;
    laz[i] %= mod;  // Take the modulus here
    sum[i] *= z;
    sum[i] %= mod;  // Take the modulus here
    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;  // Take the modulus here
    laz[i] += z;
    laz[i] %= mod;  // Take the modulus here
    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) {  // Obtain the answer; the lazy-tag code above may help with 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 the 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;
}

#include <iostream>

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

void build(int l, int r, int p) {  // Build the 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; see 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) {  // Obtain the answer, as above
  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;
}

Extensions

Segment trees have very broad applications. Common extensions and variants include:

• Persistent Segment Tree
• Various tree-of-trees structures:
  • Segment Tree over Segment Tree
  • Fenwick Tree over Segment Tree
  • Segment Tree over a Balanced Tree
  • Balanced Tree over Fenwick Tree
• Li Chao Segment Tree
• Cat Tree
• Segment Tree Beats

See the corresponding pages for details.

Application: Optimizing Graph Construction with Segment Trees

When building graph edges, we sometimes encounter a problem in which one vertex is connected to every vertex in a contiguous interval, or every vertex in a contiguous interval is connected to one vertex. Connecting the edges one by one makes the complexity explode when there are many vertices, so we use this interval properties of segment trees to optimize graph construction.

Here is a segment tree.

Every node represents an interval. Suppose we want to add edges to interval $[2, 4]$.

In some problems, an interval points to a single vertex. We can simply reverse every directed edge in the first diagram above. The upper tree is called the in-tree, and the lower one the out-tree.

#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) {  // this concept
  return t[u].lson;
}

int rs(int u) {  // this concept
  return t[u].rson;
}

void build(int &u, int l, int r) {  // this conceptpointthis concepttree
  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) {  // this conceptpointthis concepttree
  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) {  // pointthis conceptintervalthis conceptedge
  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) {  // intervalthis conceptpointthis conceptedge
  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;
}

Exercises

• luogu P3372 ［Template］ Segment Tree 1
• luogu P13825 Segment Tree 1.5 ［Dynamic Node-Opening Segment Tree］
• luogu P3373 ［Template］ Segment Tree 2
• luogu P4588 ［TJOI2018］ Mathematical Calculation
• luogu P5490 ［Template］ Sweep Line & Union of Rectangle Areas
• luogu P1471 Variance