Part 0: Introduction to Segment Trees

What is a segment tree? A segment tree is a data structure which stores information on array segments.

Didn’t catch that? No worries.

Let’s start from the beginning.

We have an array. A magical array. That can do sums. Damn fast (\(O(log n)\), to be exact). It is the MagicalSumArray.

int main(){
    MagicalSumArray a({1,3,5,7,9});
    cout << a.sum(2, 4) << endl; // a[2] + a[3] + a[4] = 21

    // Oh, it can also update damn fast (also in O(log n)).
    a.set(2, 10); // a[2] = 10

    cout << a.sum(2, 4) << endl; // a[2] + a[3] + a[4] = 26
}

Or! We can also have a MagicalProductArray, MagicalGCDArray, or even MagicalMinArray, and so on.

A segment tree can do all of those. Just think of it like a magical array and not a tree.

Just like when you code, you don’t think of a set as a binary search tree. Or priority_queue as a maximum heap. Or unordered_set as a hash table. Unless you do. Then forget what I said.

Before it can do that, it needs to know three things (to be exact, it needs a Monoid).

The type of the elements you’re storing (let’s call it S)
- int? long long? Cat?
The operation that you will use when querying (let’s call it op)
- It should be associative, i.e. op(a,op(b,c)) = op(op(a,b),c) for all a,b,c in S.
- Want a MagicalSumArray? Use int op(int a, int b){ return a + b; }
- Want a MagicalMinArray? Use int op(int a, int b){ return min(a,b); }
The identity element (let’s call it e)
- For any element x, it should satisfy op(x,e) = x and op(e,x) = x.
- Want a MagicalSumArray? Use int e(){ return 0; }
- Want a MagicalMinArray? Use int e(){ return INF; } where INF is as big (or bigger) as the maximum number you’ll use.

And here’s how we can use it. I’m going to query sums.

int op(int a, int b) { return a + b; }
int e() { return 0; }

int main(){
    vector<int> a = {1,2,3,4,5,6,7,8};
    segtree<int, op, e> seg(a);

    seg.set(3, 5);
    cout << seg.query(2, 6) << endl;
    cout << seg.query(1, 3) << endl;
}

Great!

Some Easy Practice Problems

Now, should we try out some problems?

You don’t have to understand the code above for now. Take the code and try it out on these problems:

Did you get it? Here are the sample answers:

// Static Range Sum Queries
#include <iostream>
#include <vector>
using namespace std;

// paste segtree code here

typedef long long ll;
ll op(ll a, ll b) { return a + b; }
ll e() { return 0; }

int main() {
  int n, q;
  cin >> n >> q;
  vector<ll> x(n);
  for (int i = 0; i < n; i++) cin >> x[i];

  segtree<ll, op, e> seg(x); // creating our segment tree with the vector x
  for (int i = 0; i < q; i++) {
    int a, b;
    cin >> a >> b;
    cout << seg.query(a - 1, b - 1) << endl; // querying [a,b]
  }
}

#include <iostream>
#include <vector>
using namespace std;

// paste segtree code here

// Dynamic Range Sum Queries
typedef long long ll;
ll op(ll a, ll b) { return a + b; }
ll e() { return 0; }

int main() {
  int n, q;
  cin >> n >> q;
  vector<ll> x(n);
  for (int i = 0; i < n; i++) cin >> x[i];

  segtree<ll, op, e> seg(x);
  for (int i = 0; i < q; i++) {
    int t;
    cin >> t;
    if (t == 1) {
      int k, u;
      cin >> k >> u;
      seg.set(k - 1, u); // x_k = u;
    } else {
      int a, b;
      cin >> a >> b;
      cout << seg.query(a - 1, b - 1) << endl; // querying [a,b]
    }
  }
}

For the “minimum” version of these problems, it suffices to change op and e to:

ll op(ll a, ll b) { return min(a, b); }
ll e() { return LONG_LONG_MAX; }

For the “xor” version, we can do:

ll op(ll a, ll b) { return a ^ b; }
ll e() { return 0; }

Different Types of Segment Trees

Before we start implementing it, let’s explore what other magical stuff we can do.

Applying a function to a range \([l,r]\) (Boring Name: Lazy Propogation)
- Besides querying for \([l,r]\), we can apply a function to that range
- For example, we can add/multiply a number \(x\) to \(a[l], a[l+1], ... a[r]\).
- Or we can set all \(a[l], ... a[r]\) to a new value \(y\).
Supporting a sparse array (a very large array with a lot of empty values)
- Sometimes the array is so large (maybe have size \(10^9\)) that we can’t store it in memory.
- But we know that most of the values are empty.
- We can store only the non-empty values.
Time Travel (Boring Name: Persistent Segment Tree)
- We can query the array at different points in time.
- We can go back to the past and change the array.
- We live in a science fiction world where we can have different branches of timelines.
- Honestly, I don’t see this much in contests, but it’s fun to learn and it’s not hard to understand too.

Time and Space Complexity Analysis

	Normal	Lazy	Sparse	Persistent
Space	\(O(n)\)	\(O(n)\)	\(O(k log n)\)	\(O(k log n)\)
Query	\(O(log n)\)	\(O(log n)\)	\(O(log n)\)	\(O(log n)\)
Update	\(O(log n)\)	\(O(log n)\)	\(O(log n)\)	\(O(log n)\)
Range Update	-	\(O(log n)\)	-	-

Please, just take a moment to admire how cool it is.

Implementing a Segment Tree

Finally.

Actually, that’s for another day.

Implementing a Segment Tree: to be done
Implementing a Lazy Segment Tree: to be done
Implementing a Sparse Segment Tree: to be done
Implementing a Persistent Segment Tree: to be done