What is a Segment Tree?

A segment tree is a binary tree-based advanced data structure that supports flexible range operations. Unlike a Fenwick Tree (Binary Indexed Tree) which is limited to simple point update/range query use cases, segment trees can handle range updates with point queries, and even full range updates with range queries efficiently, making it a more versatile general-purpose data structure for range problems.

Building a Segment Tree

Each node in a segment tree is responsible for managing a specific interval of the input array. We build the tree recursively by splitting the current interval into two halves, assigning each half to the left and right child nodes respectively, until we reach leaf nodes that correspond to individual elements of the input array.

A standard implementation of the build function is shown below:

void build(int node, int left, int right) {
    seg_tree[node].range_l = left;
    seg_tree[node].range_r = right;
    if (left == right) {
        seg_tree[node].sum = arr[left];
        return;
    }
    int mid = (left + right) >> 1;
    build(2 * node, left, mid);
    build(2 * node + 1, mid + 1, right);
    seg_tree[node].sum = seg_tree[2 * node].sum + seg_tree[2 * node + 1].sum;
}

For static segment trees, you should always allocate 4 times the size of your input array to avoid overflow, unless you are using dynamic node allocation.

Point Update & Range Query

Point Update

Updating a single element is done recursively: we traverse down the tree to find the leaf node corresponding to the target position, update its value, then backtrack up the tree to update the sum of all parent nodes.

void point_update(int node, int pos, int delta) {
    if (seg_tree[node].range_l == seg_tree[node].range_r) {
        seg_tree[node].sum += delta;
        return;
    }
    if (pos <= seg_tree[2 * node].range_r) {
        point_update(2 * node, pos, delta);
    } else {
        point_update(2 * node + 1, pos, delta);
    }
    seg_tree[node].sum = seg_tree[2 * node].sum + seg_tree[2 * node + 1].sum;
    return;
}

Range Query

To query the sum of a target interval, we traverse the tree from root, and return the sum of any node whose antire interval is fully contained within the target query range. We only recurse deeper into child nodes if the current node's interval partially overlaps the query range.

int range_query(int node, int q_l, int q_r) {
    if (seg_tree[node].range_l >= q_l && seg_tree[node].range_r <= q_r) {
        return seg_tree[node].sum;
    }
    if (seg_tree[node].range_r < q_l || seg_tree[node].range_l > q_r) {
        return 0;
    }
    int result = 0;
    if (seg_tree[2 * node].range_r >= q_l) {
        result += range_query(2 * node, q_l, q_r);
    }
    if (seg_tree[2 * node + 1].range_l <= q_r) {
        result += range_query(2 * node + 1, q_l, q_r);
    }
    return result;
}

Range Update & Point Query For range updates that only require point queries, we can use a simple lazy tagging approach. When adding a delta to a fully covered update interval, we just store the delta in the current node's tag, and do not recurse deeper. When querying a point, we accumulate all tags along the path from root to the target leaf node to get the final value.

Range Add Implementation

void range_add(int node, int u_l, int u_r, int delta) {
    if (seg_tree[node].range_l >= u_l && seg_tree[node].range_r <= u_r) {
        seg_tree[node].tag += delta;
        return;
    }
    int mid = (seg_tree[node].range_l + seg_tree[node].range_r) >> 1;
    if (u_l <= mid) {
        range_add(2 * node, u_l, u_r, delta);
    }
    if (u_r > mid) {
        range_add(2 * node + 1, u_l, u_r, delta);
    }
}

Point Query Implementation

int point_query(int node, int target_pos) {
    int result = seg_tree[node].tag;
    if (seg_tree[node].range_l == seg_tree[node].range_r) {
        return result;
    }
    int mid = (seg_tree[node].range_l + seg_tree[node].range_r) >> 1;
    if (target_pos <= mid) {
        return result + point_query(2 * node, target_pos);
    } else {
        return result + point_query(2 * node + 1, target_pos);
    }
}

This approach is commonly used to solve the range add point query problem from Luogu P3368. A full working template for this problem is shown below:

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;
int ans;
int a[MAXN];

struct Node {
    int l, r;
    int val;
} tr[MAXN * 4];

void build(int p, int l, int r) {
    tr[p].l = l;
    tr[p].r = r;
    tr[p].val = 0;
    if (l == r) {
        tr[p].val = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
}

void modify(int p, int l, int r, int k) {
    if (tr[p].l >= l && tr[p].r <= r) {
        tr[p].val += k;
        return;
    }
    int mid = (tr[p].l + tr[p].r) >> 1;
    if (l <= mid) modify(p << 1, l, r, k);
    if (r > mid) modify(p << 1 | 1, l, r, k);
}

void query(int p, int x) {
    ans += tr[p].val;
    if (tr[p].l == tr[p].r) return;
    int mid = (tr[p].l + tr[p].r) >> 1;
    if (x <= mid) query(p << 1, x);
    else query(p << 1 | 1, x);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y, k;
            cin >> x >> y >> k;
            modify(1, x, y, k);
        } else {
            ans = 0;
            int x;
            cin >> x;
            query(1, x);
            cout << ans << '\n';
        }
    }
    return 0;
}

Range Update & Range Query with Lazy Propagation Full support for both range updates and range queries requires the use of lazy propagation (lazy tags), which is the core concept of a fully functional segment tree. A naive approach that updates every leaf node for every range update will result in O(n) time per update, which is far too slow for large inputs. Lazy propagation solves this by deferring updates to child nodes until we actually need to access them.

The core idea is: when we need to add a delta to a range that fully covers the current node's interval, we immediately update the current node's sum (delta multiplied by the length of the intreval), add delta to the current node's lazy tag, and return without recursing deeper. We only propagate the tag down to child nodes when we need to access the children for a subsequent update or query.

Range Udpate Implementation

void range_update(int node, int u_l, int u_r, int delta) {
    if (seg_tree[node].range_l >= u_l && seg_tree[node].range_r <= u_r) {
        seg_tree[node].sum += delta * (seg_tree[node].range_r - seg_tree[node].range_l + 1);
        seg_tree[node].lazy += delta;
        return;
    }
    push_down(node);
    if (seg_tree[2 * node].range_r >= u_l) {
        range_update(2 * node, u_l, u_r, delta);
    }
    if (seg_tree[2 * node + 1].range_l <= u_r) {
        range_update(2 * node + 1, u_l, u_r, delta);
    }
    seg_tree[node].sum = seg_tree[2 * node].sum + seg_tree[2 * node + 1].sum;
    return;
}

Tag Propagation Implementation

void push_down(int node) {
    if (seg_tree[node].lazy == 0) return;
    int left = 2 * node;
    int right = 2 * node + 1;
    // Pass lazy tag to children
    seg_tree[left].lazy += seg_tree[node].lazy;
    seg_tree[right].lazy += seg_tree[node].lazy;
    // Update children's sum
    int mid = (seg_tree[node].range_l + seg_tree[node].range_r) / 2;
    seg_tree[left].sum += seg_tree[node].lazy * (mid - seg_tree[left].range_l + 1);
    seg_tree[right].sum += seg_tree[node].lazy * (seg_tree[right].range_r - mid);
    // Reset current node's lazy tag
    seg_tree[node].lazy = 0;
    return;
}

Range Query Implementation

int range_query(int node, int q_l, int q_r) {
    if (seg_tree[node].range_l >= q_l && seg_tree[node].range_r <= q_r) {
        return seg_tree[node].sum;
    }
    if (seg_tree[node].range_r < q_l || seg_tree[node].range_l > q_r) {
        return 0;
    }
    push_down(node);
    int res = 0;
    if (seg_tree[2 * node].range_r >= q_l) {
        res += range_query(2 * node, q_l, q_r);
    }
    if (seg_tree[2 * node + 1].range_l <= q_r) {
        res += range_query(2 * node + 1, q_l, q_r);
    }
    return res;
}

Note: The example code for Luogu P3368 above contains a bug, please do not copy-paste it blindly for submission.