> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Segment Trees

> Master range queries, point updates, and lazy propagation

# Segment Trees

<img src="https://mintcdn.com/devweeekends/AEOaWh79Ur7CdHHv/images/courses/cp/segment-tree-structure.svg?fit=max&auto=format&n=AEOaWh79Ur7CdHHv&q=85&s=4b2269df407278b704ff95079bd8f98b" alt="Segment Tree Structure" width="1080" height="1080" data-path="images/courses/cp/segment-tree-structure.svg" />

## Why Segment Trees?

Segment trees answer **range queries** and handle **point/range updates** in O(log n) time. They're essential for problems involving:

* Range sum/min/max/GCD queries
* Range updates (add/set all elements)
* Count elements in range satisfying condition

<Note>
  **Pattern Recognition Signals**:

  * "Query sum/min/max from L to R" → Segment tree
  * "Update element at position i" → Segment tree with point update
  * "Add x to all elements from L to R" → Lazy propagation
  * "Count elements > k in range" → Merge sort tree or segment tree with sets
</Note>

***

## Basic Segment Tree (Point Update, Range Query)

```cpp theme={null}
class SegTree {
public:
    int n;
    vector<long long> tree;
    
    SegTree(int n) : n(n), tree(4 * n, 0) {}
    
    SegTree(vector<int>& arr) : n(arr.size()), tree(4 * n) {
        build(arr, 1, 0, n - 1);
    }
    
    void build(vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
            return;
        }
        
        int mid = (start + end) / 2;
        build(arr, 2 * node, start, mid);
        build(arr, 2 * node + 1, mid + 1, end);
        
        tree[node] = tree[2 * node] + tree[2 * node + 1];  // Combine
    }
    
    void update(int idx, int val) {
        update(1, 0, n - 1, idx, val);
    }
    
    void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val;
            return;
        }
        
        int mid = (start + end) / 2;
        if (idx <= mid) {
            update(2 * node, start, mid, idx, val);
        } else {
            update(2 * node + 1, mid + 1, end, idx, val);
        }
        
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    
    long long query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
    
    long long query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return 0;  // Out of range (identity for sum)
        }
        
        if (l <= start && end <= r) {
            return tree[node];  // Fully contained
        }
        
        int mid = (start + end) / 2;
        return query(2 * node, start, mid, l, r) +
               query(2 * node + 1, mid + 1, end, l, r);
    }
};
```

### Usage

```cpp theme={null}
vector<int> arr = {1, 3, 5, 7, 9, 11};
SegTree st(arr);

cout << st.query(1, 3);  // 15 (3 + 5 + 7)
st.update(2, 10);        // arr[2] = 10
cout << st.query(1, 3);  // 20 (3 + 10 + 7)
```

***

## Segment Tree for Different Operations

Change the combine function and identity element.

```cpp theme={null}
// Range Minimum Query
long long combine(long long a, long long b) {
    return min(a, b);
}
long long identity = LLONG_MAX;

// Range Maximum Query
long long combine(long long a, long long b) {
    return max(a, b);
}
long long identity = LLONG_MIN;

// Range GCD Query
long long combine(long long a, long long b) {
    return __gcd(a, b);
}
long long identity = 0;

// Range XOR Query
long long combine(long long a, long long b) {
    return a ^ b;
}
long long identity = 0;
```

***

## Lazy Propagation (Range Updates)

When you need to update a **range** of elements, not just one.

**The Problem**: Adding a value to all elements in range \[L, R] would require O(R - L + 1) point updates, making it O(n) per update—too slow!

**The Insight**: Don't update immediately. Instead, store a "pending update" (lazy value) at a node. Only push it down to children when needed.

**How it works**:

1. **Range Update**: When updating \[L, R], if a node's range is completely inside \[L, R], mark it with a lazy value and return (don't recurse)
2. **Push Down**: Before accessing children, push the lazy value down to them
3. **Query**: Same as before, but push down lazy values as you traverse

**Visual Example** - Adding 5 to \[1, 4] in array \[1, 2, 3, 4, 5, 6]:

```
Before:                    After marking lazy=5:
       21                         21 + 5*4 = 41
      /  \                            /    \
    10    11                   10+5*2=20   11
   /  \   / \                    lazy=5    / \
  3   7  9  11                            9   11
 / \ / \                                 (children not updated yet)
1 2 3 4
```

The lazy value is only pushed down when we need to access children.

```cpp theme={null}
class LazySegTree {
public:
    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 start, int end) {
        if (lazy[node] != 0) {
            int mid = (start + end) / 2;
            
            // Push lazy value to children
            tree[2 * node] += lazy[node] * (mid - start + 1);
            tree[2 * node + 1] += lazy[node] * (end - mid);
            
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
            
            lazy[node] = 0;
        }
    }
    
    // Add val to all elements in [l, r]
    void updateRange(int l, int r, long long val) {
        updateRange(1, 0, n - 1, l, r, val);
    }
    
    void updateRange(int node, int start, int end, int l, int r, long long val) {
        if (r < start || end < l) return;
        
        if (l <= start && end <= r) {
            tree[node] += val * (end - start + 1);
            lazy[node] += val;
            return;
        }
        
        pushDown(node, start, end);
        
        int mid = (start + end) / 2;
        updateRange(2 * node, start, mid, l, r, val);
        updateRange(2 * node + 1, mid + 1, end, l, r, val);
        
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    
    long long query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
    
    long long query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0;
        
        if (l <= start && end <= r) return tree[node];
        
        pushDown(node, start, end);
        
        int mid = (start + end) / 2;
        return query(2 * node, start, mid, l, r) +
               query(2 * node + 1, mid + 1, end, l, r);
    }
};
```

***

## Range Set (Assignment) with Lazy

```cpp theme={null}
class LazySetSegTree {
public:
    int n;
    vector<long long> tree, lazy;
    vector<bool> hasLazy;
    
    LazySetSegTree(int n) : n(n), tree(4 * n, 0), 
                             lazy(4 * n, 0), hasLazy(4 * n, false) {}
    
    void pushDown(int node, int start, int end) {
        if (hasLazy[node]) {
            int mid = (start + end) / 2;
            
            tree[2 * node] = lazy[node] * (mid - start + 1);
            tree[2 * node + 1] = lazy[node] * (end - mid);
            
            lazy[2 * node] = lazy[2 * node + 1] = lazy[node];
            hasLazy[2 * node] = hasLazy[2 * node + 1] = true;
            
            hasLazy[node] = false;
        }
    }
    
    // Set all elements in [l, r] to val
    void setRange(int l, int r, long long val) {
        setRange(1, 0, n - 1, l, r, val);
    }
    
    void setRange(int node, int start, int end, int l, int r, long long val) {
        if (r < start || end < l) return;
        
        if (l <= start && end <= r) {
            tree[node] = val * (end - start + 1);
            lazy[node] = val;
            hasLazy[node] = true;
            return;
        }
        
        pushDown(node, start, end);
        
        int mid = (start + end) / 2;
        setRange(2 * node, start, mid, l, r, val);
        setRange(2 * node + 1, mid + 1, end, l, r, val);
        
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
};
```

***

## Pattern 1: Coordinate Compression + Segment Tree

**Problem**: Count distinct elements, or handle values up to 10^9.

```cpp theme={null}
// Compress values to [0, n-1]
vector<int> arr;  // Original array
vector<int> sorted_arr = arr;
sort(sorted_arr.begin(), sorted_arr.end());
sorted_arr.erase(unique(sorted_arr.begin(), sorted_arr.end()), sorted_arr.end());

auto compress = [&](int x) {
    return lower_bound(sorted_arr.begin(), sorted_arr.end(), x) - sorted_arr.begin();
};

// Now use compress(arr[i]) as index in segment tree
```

***

## Pattern 2: Count Inversions with Segment Tree

```cpp theme={null}
long long countInversions(vector<int>& arr) {
    int n = arr.size();
    
    // Coordinate compression
    vector<int> sorted_arr = arr;
    sort(sorted_arr.begin(), sorted_arr.end());
    sorted_arr.erase(unique(sorted_arr.begin(), sorted_arr.end()), sorted_arr.end());
    
    auto compress = [&](int x) {
        return lower_bound(sorted_arr.begin(), sorted_arr.end(), x) - sorted_arr.begin();
    };
    
    SegTree st(sorted_arr.size());
    long long inversions = 0;
    
    // Process from right to left
    for (int i = n - 1; i >= 0; i--) {
        int compressed = compress(arr[i]);
        inversions += st.query(0, compressed - 1);  // Count smaller elements to the right
        st.update(compressed, st.query(compressed, compressed) + 1);
    }
    
    return inversions;
}
```

***

## Pattern 3: Range Queries Offline

**Problem**: Answer queries more efficiently by processing in smart order.

```cpp theme={null}
// Process queries sorted by right endpoint
struct Query {
    int l, r, idx;
};

vector<Query> queries(q);
for (int i = 0; i < q; i++) {
    cin >> queries[i].l >> queries[i].r;
    queries[i].idx = i;
}

sort(queries.begin(), queries.end(), [](auto& a, auto& b) {
    return a.r < b.r;
});

vector<long long> answers(q);
int j = 0;

for (auto& [l, r, idx] : queries) {
    while (j <= r) {
        // Add element j to segment tree
        j++;
    }
    answers[idx] = st.query(l, r);
}
```

***

## Pattern 4: Segment Tree on Indices

**Problem**: Track positions where something is true.

```cpp theme={null}
// Find leftmost index in [l, r] where arr[i] > x
int findFirst(int node, int start, int end, int l, int r, int x) {
    if (r < start || end < l || tree[node] <= x) return -1;
    
    if (start == end) return start;
    
    int mid = (start + end) / 2;
    int left = findFirst(2 * node, start, mid, l, r, x);
    if (left != -1) return left;
    return findFirst(2 * node + 1, mid + 1, end, l, r, x);
}
```

***

## Pattern 5: 2D Segment Tree

For 2D range queries (less common, but powerful).

```cpp theme={null}
class SegTree2D {
public:
    int n, m;
    vector<vector<long long>> tree;
    
    SegTree2D(int n, int m) : n(n), m(m), tree(4 * n, vector<long long>(4 * m, 0)) {}
    
    void updateY(int nodeX, int startX, int endX, int nodeY, int startY, int endY, 
                 int x, int y, long long val) {
        if (startY == endY) {
            if (startX == endX) {
                tree[nodeX][nodeY] = val;
            } else {
                tree[nodeX][nodeY] = tree[2 * nodeX][nodeY] + tree[2 * nodeX + 1][nodeY];
            }
            return;
        }
        
        int midY = (startY + endY) / 2;
        if (y <= midY) {
            updateY(nodeX, startX, endX, 2 * nodeY, startY, midY, x, y, val);
        } else {
            updateY(nodeX, startX, endX, 2 * nodeY + 1, midY + 1, endY, x, y, val);
        }
        tree[nodeX][nodeY] = tree[nodeX][2 * nodeY] + tree[nodeX][2 * nodeY + 1];
    }
    
    void update(int x, int y, long long val) {
        updateX(1, 0, n - 1, x, y, val);
    }
    
    void updateX(int nodeX, int startX, int endX, int x, int y, long long val) {
        if (startX != endX) {
            int midX = (startX + endX) / 2;
            if (x <= midX) {
                updateX(2 * nodeX, startX, midX, x, y, val);
            } else {
                updateX(2 * nodeX + 1, midX + 1, endX, x, y, val);
            }
        }
        updateY(nodeX, startX, endX, 1, 0, m - 1, x, y, val);
    }
};
```

***

## Common Mistakes

<Warning>
  **Mistake 1: Wrong array size**
  Segment tree needs 4n space, not 2n.

  ```cpp theme={null}
  vector<long long> tree(4 * n);  // CORRECT
  ```
</Warning>

<Warning>
  **Mistake 2: Forgetting to push lazy**
  Always call pushDown before recursing in lazy segment tree.
</Warning>

<Warning>
  **Mistake 3: Wrong identity element**

  * Sum: 0
  * Min: LLONG\_MAX
  * Max: LLONG\_MIN
  * GCD: 0
</Warning>

<Warning>
  **Mistake 4: 0-indexing vs 1-indexing**
  Be consistent. The template above uses 0-indexed arrays.
</Warning>

***

## Practice Problems

### Beginner (1000-1300)

| Problem               | Pattern      | Link                                         |
| --------------------- | ------------ | -------------------------------------------- |
| Range Sum Queries     | Point update | [CSES](https://cses.fi/problemset/task/1648) |
| Range Minimum Queries | Static       | [CSES](https://cses.fi/problemset/task/1647) |
| Dynamic Range Sum     | Point update | [CSES](https://cses.fi/problemset/task/1648) |

### Intermediate (1300-1600)

| Problem              | Pattern                | Link                                         |
| -------------------- | ---------------------- | -------------------------------------------- |
| Range Update Queries | Lazy propagation       | [CSES](https://cses.fi/problemset/task/1651) |
| Range Xor Queries    | Prefix XOR             | [CSES](https://cses.fi/problemset/task/1650) |
| Salary Queries       | Coordinate compression | [CSES](https://cses.fi/problemset/task/1144) |

### Advanced (1600-1900)

| Problem                | Pattern                | Link                                         |
| ---------------------- | ---------------------- | -------------------------------------------- |
| Polynomial Queries     | Lazy with coefficients | [CSES](https://cses.fi/problemset/task/1736) |
| Range Updates and Sums | Dual lazy              | [CSES](https://cses.fi/problemset/task/1735) |

***

## Key Takeaways

<CardGroup cols={2}>
  <Card title="O(log n) Queries" icon="gauge-high">
    Both point updates and range queries in logarithmic time.
  </Card>

  <Card title="Lazy Propagation" icon="clock">
    Defer updates until needed for O(log n) range updates.
  </Card>

  <Card title="4n Space" icon="memory">
    Always allocate 4n space for the tree array.
  </Card>

  <Card title="Combine Function" icon="object-group">
    Customize for sum, min, max, GCD, or any associative operation.
  </Card>
</CardGroup>

***

## Next Up

<Card title="Chapter 18: String Algorithms" icon="arrow-right" href="/courses/competitive-programming/18-strings">
  Master hashing, KMP, Z-function, and Trie for string problems.
</Card>