13 April 2017: Segment trees

From UMCPC Wiki
Jump to: navigation, search

Segment Trees: A basic introduction

Presenter: Chang

What is a segment tree?

It is a data structure!

It is used when we have an array and want to perform changes and queries on continuous segments.

Usually supports these 2 operations:

  1. Modify one element in the array
  2. Find info about some segment

Why use a segment tree?

Consider an array of n integers with indices 0 to n

  • How to find the sum of an interval $[i, j)$?
  • How to find the min/max of an interval $[i, j)$?
  • Thoughts? Complexity?

Case 1: normal array, $O(n)$ space complexity

Querying for sum/min of interval $[i, j)$ — $O(n)$ time complexity

Modifying a value — $O(1)$ time complexity

Case 2: cumulative array, $O(n)$ space complexity

Querying for sum of interval $[i, j)$ (can’t query min) — $O(1)$ time complexity

Modifying a value — $O(n)$ time complexity

Case 3: segment tree, $O(n)$ space complexity

Querying for sum/min of interval $[i, j)$ — $O(\log n)$ time complexity

Modifying a value — $O(\log n)$ time complexity

But how is it log n?

Suppose we have an array of n elements and want to make t queries and modifications

  • Normal array and cumulative array: $O(t \cdot n)$
  • Segment tree: $O(t \log n)$

In case you didn’t already know, $\log n << n$

How to implement a segment tree?

 1  // Segtree implementation from 
 2  // http://codeforces.com/blog/entry/18051
 3  #include <stdio.h>
 4  
 5  #define N 100000 // limit for array size
 6  
 7  int n; // array size
 8  int t[2 * N];
 9  
10  void build() { // build the tree
11  	int i;
12  	for (i = n - 1; i > 0; --i) t[i] = t[i * 2] + t[i * 2 + 1];
13  }
14  
15  void modify(int p, int value) { // set value at position p
16  	for (t[p += n] = value; p > 1; p >>= 1) t[p/2] = t[p] + t[p^1];
17  	// or alternatively,
18  	// for (t[p += n] = value; p /= 2;) t[p] = t[p * 2] + t[p * 2 + 1];
19  }
20  
21  int query(int l, int r) { // sum on interval [l,r)
22  	int res = 0;
23  	for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
24  		if (l&1) res += t[l++];
25  		if (r&1) res += t[--r];
26  	}
27  	return res;
28  }
29  
30  int main() {
31  	scanf("%d", &n);
32  	int i;
33    	for (i = 0; i < n; ++i) scanf("%d", t + n + i);
34    	build();
35    	modify(0, 1);
36    	printf("%d\n", query(3, 11));
37    	return 0;
38  }

Useful pictures

Selected problems

List of more problems

References