Learn Segment Tree — Free DSA Tutorial

What is a Segment Tree

A segment tree is a binary tree built over an array where each node represents the combined information (like the sum or minimum) for a contiguous range of the array, letting you answer questions about any subrange quickly.

Example: What is a Segment Tree

#include <iostream>
using namespace std;
int main() {
	int arr[] = {2,4,5,7,8,9};
	cout << "Binary tree over the array, each node = combined info (e.g. sum) for a contiguous range";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] arr = {2,4,5,7,8,9};
		System.out.println("Binary tree over the array, each node = combined info (e.g. sum) for a contiguous range");
	}
}

arr = [2,4,5,7,8,9]
print("Binary tree over the array, each node = combined info (e.g. sum) for a contiguous range")

#include <stdio.h>
int main() {
	int arr[] = {2,4,5,7,8,9};
	printf("Binary tree over the array, each node = combined info (e.g. sum) for a contiguous range");
	return 0;
}

Range Query

To answer a query over an arbitrary range, the tree combines results from a small number of nodes that together exactly cover that range, rather than scanning every individual array element between the two endpoints.

Example: Range Query

#include <iostream>
#include <vector>
using namespace std;
vector<int> tree;
void build(vector<int>& arr, int node, int start, int end) {
	if (start == end) { tree[node] = arr[start]; return; }
	int mid = (start+end)/2;
	build(arr, 2*node, start, mid);
	build(arr, 2*node+1, mid+1, end);
	tree[node] = tree[2*node] + tree[2*node+1];
}
int query(int node, int start, int end, int l, int r) {
	if (r < start || end < l) return 0;
	if (l <= start && end <= r) return tree[node];
	int mid = (start+end)/2;
	return query(2*node, start, mid, l, r) + query(2*node+1, mid+1, end, l, r);
}
int main() {
	vector<int> arr = {2,4,5,7,8,9};
	tree.assign(24, 0);
	build(arr, 1, 0, 5);
	cout << "Sum of range [1,3]: " << query(1, 0, 5, 1, 3);
	return 0;
}

public class Main {
	static int[] tree = new int[24];
	static void build(int[] arr, int node, int start, int end) {
		if (start == end) { tree[node] = arr[start]; return; }
		int mid = (start+end)/2;
		build(arr, 2*node, start, mid);
		build(arr, 2*node+1, mid+1, end);
		tree[node] = tree[2*node] + tree[2*node+1];
	}
	static int query(int node, int start, int end, int l, int r) {
		if (r < start || end < l) return 0;
		if (l <= start && end <= r) return tree[node];
		int mid = (start+end)/2;
		return query(2*node, start, mid, l, r) + query(2*node+1, mid+1, end, l, r);
	}
	public static void main(String[] args) {
		int[] arr = {2,4,5,7,8,9};
		build(arr, 1, 0, 5);
		System.out.println("Sum of range [1,3]: " + query(1, 0, 5, 1, 3));
	}
}

arr = [2,4,5,7,8,9]
tree = [0]*24
def build(node, start, end):
    if start == end:
        tree[node] = arr[start]
        return
    mid = (start+end)//2
    build(2*node, start, mid)
    build(2*node+1, mid+1, end)
    tree[node] = tree[2*node] + tree[2*node+1]
def query(node, start, end, l, r):
    if r < start or end < l:
        return 0
    if l <= start and end <= r:
        return tree[node]
    mid = (start+end)//2
    return query(2*node, start, mid, l, r) + query(2*node+1, mid+1, end, l, r)
build(1, 0, 5)
print("Sum of range [1,3]:", query(1, 0, 5, 1, 3))

#include <stdio.h>
int arr[] = {2,4,5,7,8,9};
int tree[24];
void build(int node, int start, int end) {
	if (start == end) { tree[node] = arr[start]; return; }
	int mid = (start+end)/2;
	build(2*node, start, mid);
	build(2*node+1, mid+1, end);
	tree[node] = tree[2*node] + tree[2*node+1];
}
int query(int node, int start, int end, int l, int r) {
	if (r < start || end < l) return 0;
	if (l <= start && end <= r) return tree[node];
	int mid = (start+end)/2;
	return query(2*node, start, mid, l, r) + query(2*node+1, mid+1, end, l, r);
}
int main() {
	build(1, 0, 5);
	printf("Sum of range [1,3]: %d", query(1, 0, 5, 1, 3));
	return 0;
}

Point Update

When a single array value changes, only the O(log n) nodes on the path from that leaf up to the root need their stored values recalculated, since every other node in the tree is unaffected by that one position.

Example: Point Update

#include <iostream>
using namespace std;
int main() {
	int treeHeight = 3;
	cout << "Only " << treeHeight << " nodes on the leaf-to-root path need recalculating after one value changes";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int treeHeight = 3;
		System.out.println("Only " + treeHeight + " nodes on the leaf-to-root path need recalculating after one value changes");
	}
}

tree_height = 3
print(f"Only {tree_height} nodes on the leaf-to-root path need recalculating after one value changes")

#include <stdio.h>
int main() {
	int treeHeight = 3;
	printf("Only %d nodes on the leaf-to-root path need recalculating after one value changes", treeHeight);
	return 0;
}

Common Operations

Segment trees aren't limited to sums — the same structure answers range minimum, range maximum, range GCD, or any other operation where combining two adjacent ranges' answers is well-defined.

Example: Common Operations

#include <iostream>
using namespace std;
int main() {
	string ops[] = {"sum", "min", "max", "gcd"};
	for (string o : ops) cout << o << " ";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		String[] ops = {"sum", "min", "max", "gcd"};
		for (String o : ops) System.out.print(o + " ");
	}
}

ops = ["sum", "min", "max", "gcd"]
print(*ops)

#include <stdio.h>
int main() {
	char* ops[] = {"sum", "min", "max", "gcd"};
	for (int i = 0; i < 4; i++) printf("%s ", ops[i]);
	return 0;
}

Complexity

Both range queries and point updates run in O(log n) time, a major improvement over the O(n) it would take to recompute a range from scratch on every query in a plain array.

Example: Complexity

#include <iostream>
using namespace std;
int main() {
	cout << "Segment tree: O(log n) query and update, vs O(n) recomputing a range from scratch";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Segment tree: O(log n) query and update, vs O(n) recomputing a range from scratch");
	}
}

print("Segment tree: O(log n) query and update, vs O(n) recomputing a range from scratch")

#include <stdio.h>
int main() {
	printf("Segment tree: O(log n) query and update, vs O(n) recomputing a range from scratch");
	return 0;
}

Segment Tree

What is a Segment Tree

Range Query

Point Update

Common Operations

Complexity

Chapter Quiz — Complete all 7 topics to unlock

Login to run this code