PrevNext
Rare
 0/2

Sparse Segment Trees

Author: Andi Qu

Querying big ranges.

Focus Problem – read through this problem before continuing!


In problems where the query range is at most something like 10610^6, a normal segment tree suffices. However, as soon as we move to bigger ranges (101210^{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(logN)O(\log N) nodes, so in a sparse segment tree, we only store O(QlogN)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.)

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.
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 10910^9, so we have to use a sparse segment tree.

Luckily, lazy propagation still works here.

C++

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

It's possible to reduce the memory of a sparse segment tree to O(N)O(N), as described here.

Problems

StatusSourceProblem NameDifficultyTagsSolution
IOINormalExternal Sol
Balkan OINormal

Module Progress:

Give Us Feedback on Sparse Segment Trees!

PrevNext