Sparse Segment Trees

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

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})$

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

class SparseSegtree {
  private:
	struct Node {
		int freq = 0;
		int lazy = 0;
		Node *left = nullptr;
		Node *right = nullptr;

Index Implementation

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

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

class SparseSegtree {
  private:
	struct Node {
		int freq = 0;
		int lazy = 0;
		int left = -1;
		int right = -1;

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.