Segment trees are powerful data structures used for efficiently processing range queries and updates on arrays. There are various types of segment trees depending on the operations they support (e.g., sum, min, max, GCD, etc.) and whether they allow updates. Below are different types of segment trees with C# examples:
1. Basic Segment Tree (Sum Query)
➤ Supports:
- Range sum queries
- Point updates
Example:
class SegmentTree {
int[] tree;
int n;
public SegmentTree(int[] arr) {
n = arr.Length;
tree = new int[4 * n];
Build(arr, 0, 0, n - 1);
}
void Build(int[] arr, int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
Build(arr, 2 * node + 1, start, mid);
Build(arr, 2 * node + 2, mid + 1, end);
tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}
}
public int Query(int l, int r) => Query(0, 0, n - 1, l, r);
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 + 1, start, mid, l, r) + Query(2 * node + 2, mid + 1, end, l, r);
}
public void Update(int index, int value) => Update(0, 0, n - 1, index, value);
void Update(int node, int start, int end, int idx, int val) {
if (start == end) {
tree[node] = val;
} else {
int mid = (start + end) / 2;
if (idx <= mid) Update(2 * node + 1, start, mid, idx, val);
else Update(2 * node + 2, mid + 1, end, idx, val);
tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}
}
}
2. Segment Tree for Minimum (or Maximum) Query
➤ Supports:
- Range min/max queries
- Point updates
Min Segment Tree Example:
class MinSegmentTree {
int[] tree;
int n;
public MinSegmentTree(int[] arr) {
n = arr.Length;
tree = new int[4 * n];
Build(arr, 0, 0, n - 1);
}
void Build(int[] arr, int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
Build(arr, 2 * node + 1, start, mid);
Build(arr, 2 * node + 2, mid + 1, end);
tree[node] = Math.Min(tree[2 * node + 1], tree[2 * node + 2]);
}
}
public int Query(int l, int r) => Query(0, 0, n - 1, l, r);
int Query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return int.MaxValue;
if (l <= start && end <= r) return tree[node];
int mid = (start + end) / 2;
return Math.Min(Query(2 * node + 1, start, mid, l, r), Query(2 * node + 2, mid + 1, end, l, r));
}
}
3. Lazy Segment Tree (for Range Updates)
➤ Supports:
- Range updates
- Range queries
- Useful when updates are frequent.
Example: Range Addition and Range Sum
class LazySegmentTree {
int[] tree, lazy;
int n;
public LazySegmentTree(int[] arr) {
n = arr.Length;
tree = new int[4 * n];
lazy = new int[4 * n];
Build(arr, 0, 0, n - 1);
}
void Build(int[] arr, int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
Build(arr, 2 * node + 1, start, mid);
Build(arr, 2 * node + 2, mid + 1, end);
tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}
}
void Push(int node, int start, int end) {
if (lazy[node] != 0) {
tree[node] += (end - start + 1) * lazy[node];
if (start != end) {
lazy[2 * node + 1] += lazy[node];
lazy[2 * node + 2] += lazy[node];
}
lazy[node] = 0;
}
}
public void UpdateRange(int l, int r, int val) => UpdateRange(0, 0, n - 1, l, r, val);
void UpdateRange(int node, int start, int end, int l, int r, int val) {
Push(node, start, end);
if (r < start || end < l) return;
if (l <= start && end <= r) {
lazy[node] += val;
Push(node, start, end);
return;
}
int mid = (start + end) / 2;
UpdateRange(2 * node + 1, start, mid, l, r, val);
UpdateRange(2 * node + 2, mid + 1, end, l, r, val);
tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}
public int Query(int l, int r) => Query(0, 0, n - 1, l, r);
int Query(int node, int start, int end, int l, int r) {
Push(node, start, end);
if (r < start || end < l) return 0;
if (l <= start && end <= r) return tree[node];
int mid = (start + end) / 2;
return Query(2 * node + 1, start, mid, l, r) + Query(2 * node + 2, mid + 1, end, l, r);
}
}
Certainly! Let’s explore Persistent Segment Trees and Segment Tree Beats with C# examples.
4. Persistent Segment Tree (Functional Tree)
➤ Concept:
A Persistent Segment Tree allows you to maintain multiple versions of the segment tree, enabling access to historical data without modifying the existing structure. Each update creates a new version, preserving the previous ones.
➤ C# Implementation:
using System;
class PersistentSegmentTree
{
class Node
{
public int Value;
public Node Left, Right;
public Node(int value = 0) { Value = value; }
}
private int[] arr;
private Node[] versions;
private int n;
public PersistentSegmentTree(int[] input)
{
n = input.Length;
arr = new int[n];
Array.Copy(input, arr, n);
versions = new Node[n + 1];
versions[0] = Build(0, n - 1);
}
private Node Build(int l, int r)
{
if (l == r)
return new Node(arr[l]);
int m = (l + r) / 2;
Node left = Build(l, m);
Node right = Build(m + 1, r);
return new Node(left.Value + right.Value) { Left = left, Right = right };
}
public void Update(int version, int idx, int value)
{
versions[version + 1] = Update(versions[version], 0, n - 1, idx, value);
}
private Node Update(Node prev, int l, int r, int idx, int value)
{
if (l == r)
return new Node(value);
int m = (l + r) / 2;
Node left = prev.Left, right = prev.Right;
if (idx <= m)
left = Update(prev.Left, l, m, idx, value);
else
right = Update(prev.Right, m + 1, r, idx, value);
return new Node(left.Value + right.Value) { Left = left, Right = right };
}
public int Query(int version, int l, int r)
{
return Query(versions[version], 0, n - 1, l, r);
}
private int Query(Node node, int nl, int nr, int ql, int qr)
{
if (ql > nr || qr < nl)
return 0;
if (ql <= nl && nr <= qr)
return node.Value;
int mid = (nl + nr) / 2;
return Query(node.Left, nl, mid, ql, qr) + Query(node.Right, mid + 1, nr, ql, qr);
}
}
class Program
{
static void Main()
{
int[] data = { 1, 2, 3, 4, 5 };
var pst = new PersistentSegmentTree(data);
pst.Update(0, 2, 10); // Version 1: Update index 2 to 10
pst.Update(1, 4, 20); // Version 2: Update index 4 to 20
Console.WriteLine(pst.Query(0, 0, 4)); // Query in Version 0
Console.WriteLine(pst.Query(1, 0, 4)); // Query in Version 1
Console.WriteLine(pst.Query(2, 0, 4)); // Query in Version 2
}
}
➤ Explanation:
- Node Class: Represents each node in the segment tree.
- Build Method: Constructs the initial segment tree.
- Update Method: Creates a new version of the segment tree with the updated value.
- Query Method: Retrieves the sum of elements in a given range for a specific version.
➤ Supports:
- Versioned updates
- Access to historical data
- Useful in offline queries, immutable structures.
5. Segment Tree Beats
➤ Concept:
Segment Tree Beats is an advanced technique used to handle range queries with complex conditions, such as finding the minimum value in a range that is greater than a specified threshold.
➤ C# Implementation:
using System;
class SegmentTreeBeats
{
private int[] arr;
private int[] tree;
private int n;
public SegmentTreeBeats(int[] input)
{
n = input.Length;
arr = new int[n];
Array.Copy(input, arr, n);
tree = new int[4 * n];
Build(0, 0, n - 1);
}
private void Build(int node, int start, int end)
{
if (start == end)
{
tree[node] = arr[start];
}
else
{
int mid = (start + end) / 2;
Build(2 * node + 1, start, mid);
Build(2 * node + 2, mid + 1, end);
tree[node] = Math.Min(tree[2 * node + 1], tree[2 * node + 2]);
}
}
public void Update(int idx, int value)
{
Update(0, 0, n - 1, idx, value);
}
private void Update(int node, int start, int end, int idx, int value)
{
if (start == end)
{
arr[idx] = value;
tree[node] = value;
}
else
{
int mid = (start + end) / 2;
if (start <= idx && idx <= mid)
Update(2 * node + 1, start, mid, idx, value);
else
Update(2 * node + 2, mid + 1, end, idx, value);
tree[node] = Math.Min(tree[2 * node + 1], tree[2 * node + 2]);
}
}
public int Query(int l, int r)
{
return Query(0, 0, n - 1, l, r);
}
private int Query(int node, int start, int end, int l, int r)
{
if (r < start || end < l)
return int.MaxValue;
if (l <= start && end <= r)
return tree[node];
int mid = (start + end) / 2;
int p1 = Query(2 * node + 1, start, mid, l, r);
int p2 = Query(2 * node + 2, mid + 1, end, l, r);
return Math.Min(p1, p2);
}
}
class Program
{
static void Main()
{
int[] data = { 1, 2, 3, 4, 5 };
var stb = new SegmentTreeBeats(data);
stb.Update(2, 10); // Update index 2 to 10
Console.WriteLine(stb.Query(0, 4)); // Query the minimum value in the range [0, 4]
}
}
Supports more advanced operations:
* Range minimum with conditional update (e.g., `min(x, val)`)
* Complex range statistics
Summary Table
| Type | Supports | Update Type | Use Case |
|---|---|---|---|
| Sum Segment Tree | Range sum | Point update | Cumulative sums |
| Min/Max Segment Tree | Range min/max | Point update | Min/max over intervals |
| Lazy Segment Tree | Range sum/min with updates | Range updates | Batch operations (e.g., add 5) |
| Persistent Segment Tree | Query historical versions | Persistent | Versioning |
| Advanced Segment Trees | Custom/complex operations | Depends | Specialized needs |