Segment tree, here are all the key points you need to know.

The cover image is unrelated to the text; the author happened to be listening while writing this blog.

1. The Significance of Segment Trees#

A segment tree is a data structure that maintains interval information, allowing operations such as point updates, interval updates, and interval queries to be performed with a time complexity of $O(logn)$ .

2. Principle of Segment Trees#

A segment tree is a binary search tree. It employs a divide-and-conquer approach, where problems that satisfy interval addition can be continuously split into smaller subproblems until they can be solved directly.

[!NOTE]
What is interval addition?
A problem satisfies interval addition if the answer for the interval [L, R] can be obtained by merging the answers for [L, M] and [M+1, R].

The design idea of the segment tree can be represented by the following flowchart. For a problem with an interval length of $[1,10]$ , it can be split into smaller subproblems of minimum length 1 as shown in the diagram.
Segment Tree Material

To solve practical problems, we introduce a value variable to represent the sum of elements in the interval (assuming the elements are of integer type, and the sum is within the range of long long).

Tree Construction Code Implementation#

#define range 100000;
long long values[range];// Simulate an interval
struct node{
  int l, r;
  int value;
  int lazy;// Lazy tag for controlling interval updates, to be discussed later
}node[4 * range];// The maximum length of the tree is 4 * range
void push_up(int i){
  node[i].value = node[i << 1].value + node[i << 1 | 1].value;
}
/**
  * @param 
  i: Current tree's root representing the root node of the current tree construction
  l: Current node's left interval
  r: Current node's right interval
  */
void build(int i, int l, int r){
  node[i] = { l, r, 0, 0 };
  // Already the smallest interval
  if(l == r){
    node[i].value = values[l];
    return ;
  }
  int mid = (l + r) >> 1;
  build(i << 1, l, mid);
  build(i << 1 | 1, mid + 1, r);
  push_up(i);
  return node[i].value;
}

3. Operations on Segment Trees#

As mentioned above, segment trees are designed to perform interval operations, where only modify and query operations can be completed.

Interval Query#

The query operation is very simple. Given a query interval $[l, r]$ , start searching from the root node. If the node's interval falls within the query interval, add its value; otherwise, if there is an intersection, continue querying the child nodes.

long long query(int i,int l,int r){  
  int rangeL = node[i].l;  
  int rangeR = node[i].r;  
  int mid = (rangeL + rangeR) >> 1;  
  int ans = 0;  
  if(l <= rangeL && r >= rangeR){  
    return node[i].value;  
  }  
  // Intersection with the left child interval  
  if(l <= mid){  
     ans += query(i << 1, l, r);  
  }  
  // Intersection with the right child interval  
  if(r > mid){  
     ans += query(i << 1 | 1, l, r);  
  }  
  return ans;  
}

Modification#

First, let's discuss point modification. Point modification is done by performing a DFS from the root element to find the target point. It is important to note that all nodes along the path must be updated synchronously.

void point_modify(int i, int target, int k){  
  int rangeL = node[i].l;  
  int rangeR = node[i].r;  
  if(rangeL == rangeR){// Found the target point  
    node[target].value += k;// Operation is arbitrary  
  }  
  int mid = (rangeL + rangeR) >> 1;  
  if(target <= mid){  
    modify(i << 1, target, k);  
  }  
  else{  
    modify(i << 1 | 1, target, k);  
  }  
  // Update the path  
  push_up(i);  
}

Interval modification cannot use this method, as it would lead to a time complexity of $O(nlogn)$ , which is unacceptable.
Thus, a method is designed to only query large intervals without querying the smallest nodes during the search process, and a variable lazytag is used to store the modification value. When operating on a subset of the interval, the lazytag is passed down to modify the values of the subintervals.
Code implementation:

void push_down(int i, int l, int r){  
  if(node[i].lazy){  
    int mid=(l+r)>>1;  
    node[i<<1].lazy = node[i].lazy;  
    node[i<<1|1].lazy = node[i].lazy;  
    // Pass down the lazy tag  
    node[i<<1].value += node[i].lazy * (mid - l + 1);  
    node[i<<1|1].value += node[i].lazy * (r - mid);  
    // Update value  
    node[i].lazy = 0;  
  }  
}  

void range_modify(int i, int l, int r, int k){  
  int rangeL = node[i].l;  
  int rangeR = node[i].r;  
  if(l >= rangeL && r <= rangeR){  
    node[i].lazy = k;  
    node[i].value += k * (r - l + 1);  
    return ;  
  }  
  // Pass the modification to child nodes  
  push_down(i, rangeL, rangeR);  
  int mid = (rangeL + rangeR) >> 1;  
  if(l <= mid){  
    range_modify(i << 1, l, r, k);  
  }  
  if(r > mid){  
    range_modify(i << 1 | 1, l, r, k);  
  }  
  // Update the path  
  push_up(i);  
}  

long long range_query(int i,int l,int r){  
  int rangeL = node[i].l;  
  int rangeR = node[i].r;  
  // Pass down the lazy tag to child nodes  
  push_down(i, rangeL, rangeR);  
  int mid = (rangeL + rangeR) >> 1;  
  int ans = 0;  
  if(l <= rangeL && r >= rangeR){  
    return node[i].value;  
  }  
  // Intersection with the left child interval  
  if(l <= mid){  
     ans += range_query(i << 1, l, r);  
  }  
  // Intersection with the right child interval  
  if(r > mid){  
     ans += range_query(i << 1 | 1, l, r);  
  }  
  return ans;  
}

Done!#

[!TIP]
You can try the knowledge you've learned in Luogu Template Problem 1.
The above code does not guarantee AC.