# Sparse Segment Trees

Author: Andi Qu

Querying big ranges.

### Prerequisites

In problems where the query range is at most something like $10^6$, a normal segment tree suffices. However, as soon as we move to bigger ranges ($10^{12}$ in some cases), a normal segment tree results in MLE.

Luckily, we can still use a segment tree to solve these types of problems. The main idea is that we don't have to store all the nodes at all times - we create nodes only when needed. In a normal segment tree, an update only affects $\mathcal{O}(\log N)$ nodes, so in a sparse segment tree, we only store $\mathcal{O}(Q \log N)$ nodes!

We can implement this efficiently using pointers to a node's children - just like a trie! (Then again, a segment tree is basically a fancier binary trie.)

An alternative is to implement the nodes using indices and an array to keep track of each node. This is typically faster than using pointers, although is slightly less natural to implement.

## Resources

### This section is not complete.

Resources | ||||
---|---|---|---|---|

Benq | ||||

cp-algo |

### Pro Tip

Sparse Segment Tree is more commonly referred to as "Dynamic Segment Tree."

## Solution

We need to support two operations on a range:

- Count the number of red-ripe trees in a range (range sum)
- Set all trees in a range to red-ripe (range paint)

We can use a segment tree with lazy propagation to solve this, but the query range is up to $10^9$, so we have to use a sparse segment tree.

Luckily, lazy propagation still works here.

### Pointer Implementation

**Time Complexity:** $\mathcal{O}(Q\log{N})$

C++

#include <bits/stdc++.h>using namespace std;class SparseSegtree {private:struct Node {int freq = 0;int lazy = 0;Node *left = nullptr;Node *right = nullptr;

### Warning!

This implementation is not garbage collected, so the tree nodes aren't deleted even if the instance of the segment tree is taken out of scope.

### Index Implementation

**Time Complexity:** $\mathcal{O}(Q\log{N})$

C++

#include <bits/stdc++.h>using namespace std;class SparseSegtree {private:struct Node {int freq = 0;int lazy = 0;int left = -1;int right = -1;

### Optional

It's possible to reduce the memory of a sparse segment tree to $\mathcal{O}(Q)$, as described here.

### Problems

Some of these problems are solvable with a normal segment tree if you use
coordinate compression. Sparse segment trees are rarely ever *required* to solve
a particular problem, but they can make things a lot more convenient.

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

IOI | Normal | ## Show TagsLazy SegTree, Sparse Segtree | |||

Balkan OI | Normal |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!