Segment trees look intimidating at first.

But once you see the structure, every problem uses
the same skeleton — only the merge operation changes.

Here is the complete guide.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
WHEN TO USE A SEGMENT TREE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Use a segment tree when you need BOTH:
→ Range queries (sum/min/max over [l, r])
→ Updates (to elements or ranges)

If no updates → use prefix sum (simpler, O(1) query)
If only point updates + range sum → Fenwick Tree (BIT) is simpler
If range min/max queries → segment tree (BIT cannot do this)
If range updates → segment tree with lazy propagation

Keywords: "range sum/min/max after updates", "mutable",
"update range", "query range"

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
HOW THE STRUCTURE WORKS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

A segment tree is a binary tree stored in an array of size 4*n.

tree[1] = root → stores answer for the full array [0, n-1]
tree[2i] = left child (covers left half)
tree[2i + 1] = right child (covers right half)
Leaves = individual elements

Each internal node stores the MERGED answer of its two children.
What "merged" means depends on the problem (sum, min, max, etc.).

Index:       1
           /   \
          2     3
         / \   / \
        4   5 6   7   ← leaf nodes = nums[0..3]

Build:  O(n)       — fill all nodes bottom-up
Update: O(log n)   — update one path from leaf to root
Query:  O(log n)   — combine at most O(log n) nodes

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
THERE ARE 3 TYPES OF SEGMENT TREE PROBLEMS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

TYPE 1 — POINT UPDATE + RANGE SUM QUERY
TYPE 2 — POINT UPDATE + RANGE MIN/MAX QUERY
TYPE 3 — RANGE UPDATE + RANGE QUERY (Lazy Propagation)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
TYPE 1 — POINT UPDATE + RANGE SUM QUERY
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

When to use:
→ Update a single index
→ Query the sum of any range [l, r]

THE TEMPLATE:

struct SegTree {
    int n;
    vector<long long> tree;

    SegTree(int n) : n(n), tree(4 * n, 0) {}

    void build(vector<int>& nums, int node, int lo, int hi) {
        if (lo == hi) { tree[node] = nums[lo]; return; }
        int mid = lo + (hi - lo) / 2;
        build(nums, 2*node,   lo,    mid);
        build(nums, 2*node+1, mid+1, hi);
        tree[node] = tree[2*node] + tree[2*node+1];   // merge = sum
    }

    void update(int node, int lo, int hi, int idx, long long val) {
        if (lo == hi) { tree[node] = val; return; }
        int mid = lo + (hi - lo) / 2;
        if (idx <= mid) update(2*node,   lo,    mid, idx, val);
        else update(2*node+1, mid+1, hi,  idx, val);
        tree[node] = tree[2*node] + tree[2*node+1];   // update merge
    }

    long long query(int node, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) return 0;               // out of range
        if (l <= lo && hi <= r) return tree[node];    // fully in range
        int mid = lo + (hi - lo) / 2;
        return query(2*node,   lo,    mid, l, r) +
               query(2*node+1, mid+1, hi,  l, r);
    }
};

// Usage:
SegTree st(n);
st.build(nums, 1, 0, n-1);
st.update(1, 0, n-1, idx, newVal);
long long ans = st.query(1, 0, n-1, l, r);

The three query cases (memorize these):

r < lo || hi < l   → segment is completely outside query range → return 0
l <= lo && hi <= r  → segment is completely inside query range  → return tree[node]
otherwise           → partial overlap → recurse on both children, sum results

EXAMPLE — Range Sum Query Mutable
https://leetcode.com/problems/range-sum-query-mutable

Exactly the template above. Build once, then handle two operations:
update(i, val) → point update
sumRange(l, r) → range sum query

class NumArray {
    SegTree st;
    int n;
public:
    NumArray(vector<int>& nums) : n(nums.size()), st(nums.size()) {
        st.build(nums, 1, 0, n-1);
    }
    void update(int i, int val) { st.update(1, 0, n-1, i, val); }
    int sumRange(int l, int r)  { return st.query(1, 0, n-1, l, r); }
};

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
TYPE 2 — POINT UPDATE + RANGE MIN/MAX QUERY
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

When to use:
→ Same as Type 1 but query asks for minimum or maximum, not sum

Only TWO lines change from the sum template:
The merge operation: min/max instead of +
The out-of-range return value: INT_MAX (for min) or INT_MIN (for max)

RANGE MIN TEMPLATE (only the changed lines):

// out of range → return INT_MAX (neutral for min)
if (r < lo || hi < l) return INT_MAX;

// merge = take min of two children
tree[node] = min(tree[2*node], tree[2*node+1]);

RANGE MAX TEMPLATE:

// out of range → return INT_MIN (neutral for max)
if (r < lo || hi < l) return INT_MIN;

// merge = take max of two children
tree[node] = max(tree[2*node], tree[2*node+1]);

EXAMPLE — Falling Squares
https://leetcode.com/problems/falling-squares

Each square drops onto the tallest existing square below it.
After placing each square, query max height in its range.
Then update that range with the new max height.

Coordinate compression: positions can be huge (up to 10^8),
but there are at most 2 * squares.size() distinct x-coordinates.
Map them to indices 0..m-1, build segment tree of size m.

EXAMPLE — Sliding Window Maximum
https://leetcode.com/problems/sliding-window-maximum

Can be solved with a deque (simpler), but range max segment tree also works.
For each window [l, r], query max in [l, r].

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
TYPE 3 — RANGE UPDATE + RANGE QUERY (LAZY PROPAGATION)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

When to use:
→ Add/set a value to ALL elements in a range
→ Then query sum/min/max of a range

The problem with naive range update: updating every element in [l, r]
individually takes O(n) per update → too slow.

Lazy propagation defers updates to children until they are actually needed.
Each node stores a "lazy" value: a pending update not yet pushed to children.

THE KEY IDEA:

When updating a range: if the current node's range is fully covered,
update this node and store the pending value in lazy[node].
Do NOT go to the children yet.

When you DO need to visit children (query or partial update):
PUSH DOWN the lazy value to children first.

LAZY TEMPLATE (range add + range sum):

struct LazySegTree {
    int n;
    vector<long long> tree, lazy;

    LazySegTree(int n) : n(n), tree(4*n, 0), lazy(4*n, 0) {}

    void pushDown(int node, int lo, int hi) {
        if (lazy[node] == 0) return;
        int mid = lo + (hi - lo) / 2;
        // push lazy to left child
        tree[2*node]   += lazy[node] * (mid - lo + 1);
        lazy[2*node]   += lazy[node];
        // push lazy to right child
        tree[2*node+1] += lazy[node] * (hi - mid);
        lazy[2*node+1] += lazy[node];
        // clear lazy at current node
        lazy[node] = 0;
    }

    void update(int node, int lo, int hi, int l, int r, long long val) {
        if (r < lo || hi < l) return;
        if (l <= lo && hi <= r) {
            tree[node] += val * (hi - lo + 1);   // update sum for this range
            lazy[node] += val;                    // defer to children
            return;
        }
        pushDown(node, lo, hi);                  // push before going deeper
        int mid = lo + (hi - lo) / 2;
        update(2*node,   lo,    mid, l, r, val);
        update(2*node+1, mid+1, hi,  l, r, val);
        tree[node] = tree[2*node] + tree[2*node+1];
    }

    long long query(int node, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) return 0;
        if (l <= lo && hi <= r) return tree[node];
        pushDown(node, lo, hi);                  // push before going deeper
        int mid = lo + (hi - lo) / 2;
        return query(2*node,   lo,    mid, l, r) +
               query(2*node+1, mid+1, hi,  l, r);
    }
};

WHY tree[node] += val * (hi - lo + 1)?
tree[node] stores the SUM of its range.
If you add val to every element in a range of size (hi-lo+1),
the sum increases by val * (hi - lo + 1).

EXAMPLE — My Calendar III
https://leetcode.com/problems/my-calendar-iii

Book events as range adds of +1. Query max overlap in any range.
This is range add + range max query with lazy propagation.

For range max lazy:

    tree[node] = max value in range.
    lazy[node] = pending add to all children.
    pushDown: tree[child] += lazy[node], lazy[child] += lazy[node].
    merge: tree[node] = max(tree[2*node], tree[2*node+1]).

EXAMPLE — Range Module
https://leetcode.com/problems/range-module

Track which ranges are "tracked" (1) or not (0).
addRange → range set to 1
removeRange → range set to 0
queryRange → check if all values in range are 1

This uses range assign (set) lazy, not range add.
lazy[node] stores the value to assign (-1 = no pending assignment).

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
COORDINATE COMPRESSION — WHEN VALUES ARE HUGE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Problem: positions can be up to 10^9 but there are only n queries.
Solution: map the distinct values to indices 0..m-1.

vector<int> coords;
for (auto& q : queries) {
    coords.push_back(q[0]);
    coords.push_back(q[1]);
}
sort(coords.begin(), coords.end());
coords.erase(unique(coords.begin(), coords.end()), coords.end());

// map original value to compressed index
auto getIdx = [&](int val) {
    return lower_bound(coords.begin(), coords.end(), val) - coords.begin();
};

// build segment tree of size coords.size()

Use this when: positions are large but number of distinct positions is small.
Problems: Falling Squares, Range Module, Count of Smaller Numbers After Self.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
HOW TO IDENTIFY WHICH TYPE — DECISION GUIDE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

• Do you need range updates (update a whole range at once)?
  → YES → Type 3 (Lazy Propagation)
  → NO → Type 1 or Type 2

• What does your query return?
  → Sum → Type 1 (range sum + point update)
  → Min → Type 2 (range min, return INT_MAX for out-of-range)
  → Max → Type 2 (range max, return INT_MIN for out-of-range)

• Are the coordinates huge (up to 10^8 or 10^9)?
  → YES → use coordinate compression first

• Could a simpler structure work?
  → No updates at all → prefix sum array (O(1) query)
  → Point update + range sum → Fenwick/BIT (simpler code)
  → Range update or min/max → segment tree is the right tool

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
COMMON MISTAKES AND HOW TO AVOID THEM
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

• MISTAKE 1 — Tree size too small
  Always allocate tree of size 4n, not 2n.
  2n only works for perfect binary trees.
  4n is always safe.

• MISTAKE 2 — Forgetting pushDown before recursing into children
  In lazy propagation, before you recurse into children
  (for either update or query), you MUST call pushDown first.
  Without it, children have stale values and queries return wrong results.

• MISTAKE 3 — Wrong out-of-range return value
  For sum → return 0 (neutral element for addition)
  For min → return INT_MAX (neutral element for min)
  For max → return INT_MIN (neutral element for max)
  Returning 0 for a min query will incorrectly affect the result.

• MISTAKE 4 — Wrong lazy update formula
  For range add + sum tree:
  tree[node] += lazy * range_size (not just += lazy)
  The sum of a range increases by lazy * (number of elements in range).

• MISTAKE 5 — Using 0-indexed vs 1-indexed inconsistently
  This template uses 1-indexed nodes (root = node 1).
  The input array is 0-indexed (leaves cover [0, n-1]).
  The node indices and the array indices are different things.
  Don't confuse them.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PRACTICE PROBLEMS — IN ORDER
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

• Type 1 — Point Update + Range Sum
  Range Sum Query Mutable
  https://leetcode.com/problems/range-sum-query-mutable

  Count of Smaller Numbers After Self
  https://leetcode.com/problems/count-of-smaller-numbers-after-self

• Type 2 — Point Update + Range Min/Max
  Sliding Window Maximum
  https://leetcode.com/problems/sliding-window-maximum

  Falling Squares
  https://leetcode.com/problems/falling-squares

• Type 3 — Lazy Propagation
  My Calendar I
  https://leetcode.com/problems/my-calendar-i

  My Calendar III
  https://leetcode.com/problems/my-calendar-iii

  Range Module (Hard)
  https://leetcode.com/problems/range-module

  Count of Range Sum (Hard)
  https://leetcode.com/problems/count-of-range-sum

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
THE SEGMENT TREE CHEAT SHEET — ONE LINE EACH
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

• Always allocate 4*n nodes

• Root = node 1, left = 2i, right = 2i+1

• Three query cases: outside → neutral, inside → return, partial → split

• Change the merge and neutral value to switch between sum/min/max

• Lazy propagation → pushDown before recursing into children

• Range add to sum tree → tree[node] += lazy * (hi - lo + 1)

• Huge coordinates → compress to indices first

• No updates needed → prefix sum

• Sum + point updates → Fenwick Tree (BIT) is simpler

• Min/max queries → segment tree

• Range updates → segment tree + lazy propagation

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Drop a comment if anything is unclear.
I will write a dedicated post on any type you want.