Introduction to Segment Trees

Segment trees are powerful data structures used in competitive programming. They allow us to perform range queries and updates in $O(\log N)$ time.

Math Support

We can use LaTeX for math: When we have a range $[L, R]$, the mid point is $M = \lfloor (L+R)/2 \rfloor$. The recurrence relation for time complexity is often: $T(n) = 2T(n/2) + O(1)$

Code Highlighting

Here is how you initialize a segment tree in C++:

#include <vector>
using namespace std;

const int MAXN = 100005;
int tree[4 * MAXN];

void build(int node, int start, int end, const vector<int>& a) {
    if (start == end) {
        tree[node] = a[start];
        return;
    }
    int mid = (start + end) / 2;
    build(2 * node, start, mid, a);
    build(2 * node + 1, mid + 1, end, a);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

Lazy Propagation

Lazy propagation is used when we need to update a range of elements. We maintain a lazy array to store pending updates. $O(log N)$ per update and $O(log N)$ per query.