Tree Data Structure

Segment Tree

A segment tree is typically used to store a set of intervals, such as the start and end times of events or the positions of objects in a two-dimensional space.

• Each node in the tree represents a particular interval, and the children of a node represent sub-intervals of the parent interval
• Allows for efficient querying and updating of the data, as the tree can be searched and traversed to find the relevant intervals.

Resources:

• https://cp-algorithms.com/data_structures/segment_tree.html

4 N or 2N?

Eric Pei reports 4N to be faster https://ericpei.ca/posts/segment-tree/

Todo problems:

• https://codeforces.com/blog/entry/71925
• https://codeforces.com/blog/entry/22616

A Segment Tree is a more general Fenwick Tree that can support other queries (more than range queries), such as a Range Minimum Query (RMQ).

Implementation

Erichto gave a really good visualization, see it as a binary tree.

We store a segment tree as an array of $2n$ elements where $n$ is the size of the original array and a power of two.

The tree nodes are stored from top to bottom:

• tree[1] is the top node, tree[2] and tree[3] are its children, and so on
• tree[n] to tree[2n−1] correspond to the values of the original array on the bottom level of the tree

To access the child and parents:

• Parent: the parent of tree[k] $\leftarrow$ tree[k/2]
• Children: tree[k] $\to$ tree[2k] and tree[2k+1]
  • even = left child
  • odd = right child

We always want to be on the left child node for the left side, and right child node on the right side so that the parent is representative.

Why use 1-indexing?

When we do Heap as an array, it seems to be 0-indexed. Both work. If you do 0-indexed,you need to use $2k+1$ instead of $2k$ to get the children node.

To construct the tree

for (int i=0;i<m;i++) {
	cin >> p_min[m+i];
	p_max[m+i] = p_min[m+i];
}
for (int i=m-1;i>=0; i--) {
	p_min[i] = min(p_min[2*i], p_min[2*i + 1]);
	p_max[i] = max(p_max[2*i], p_max[2*i + 1]);
}

Operations:

int sum(int a, int b) { 
	a += n; 
	b += n; 
	int s = 0; 
	while (a <= b) { 
		if (a%2 == 1) s += tree[a++]; 
		if (b%2 == 0) s += tree[b--]; 
		a /= 2; // Climb up to parent
		b /= 2;
	
	} 
	return s; 
}
 
void add(int k, int x) { 
	k += n; tree[k] += x; 
	for (k /= 2; k >= 1; k /= 2) { 
		tree[k] = tree[2*k]+tree[2*k+1]; 
	} 
}