# Sparse Segment Trees

Author: Andi Qu

### Prerequisites

Querying big ranges.

Focus Problem – read through this problem before continuing!

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.

## Resources

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 $O(gN)$ nodes, so in a sparse segment tree, we only store $O(QgN)$ 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.)

### This section is not complete.

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

Benq |

## 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.

C++

#include <bits/stdc++.h>#pragma GCC optimize("O3")#define FOR(i, x, y) for (int i = x; i < y; i++)#define MOD 1000000007typedef long long ll;using namespace std;struct Node {int sum, lazy, tl, tr, l, r;Node() : sum(0), lazy(0), l(-1), r(-1) {}

It's possible to reduce the memory of a sparse segment tree to $O(N)$, 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 | Solution | URL |
---|---|---|---|---|---|---|

IOI | Normal | External Sol | ||||

Balkan OI | Normal | |||||

JOI | Hard | ## Show TagsDP, LIS, Segtree | View Solution |

### 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!

## Give Us Feedback on Sparse Segment Trees!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.