One of the techniques for efficiently solving problems in algorithm competitions or coding interviews is the Segment Tree.
In this article, we will explore the basic concepts of segment trees and how to use them through practical problems. Segment trees can be very useful in interval query problems.
In particular, they can efficiently handle operations such as range sum, range minimum/maximum, and range updates.
What is a Segment Tree?
A segment tree is a data structure used to efficiently manage information about intervals of an array.
It allows for query operations and updates on specific intervals to be processed in logarithmic time complexity.
A segment tree is generally structured as a binary tree, where each node stores information about a specific interval.
Structure of a Segment Tree
The segment tree consists of the following structure:
- Leaf Nodes: Represent each element of the array.
- Internal Nodes: Represent the information of intervals based on the information of their child nodes (leaf nodes). For example, they store sums, minima, or maxima of their leaf nodes.
Problem Introduction
Now, let’s introduce an algorithm problem that can be solved using a segment tree.
Problem Description
Write a program that efficiently handles the following two operations on a given integer array.
- Range Sum Query: Calculate the sum of a specific range [l, r] in the array.
- Range Update: Update the value at a specific index in the array and reflect changes accordingly.
Input Format
The first line contains the size of the array N and the number of queries M. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000)
Following this, N integers are given for the array, and then M queries are provided.
The format of the queries is as follows:
- 1 l r: Outputs the sum from index l to r of the array (1 ≤ l ≤ r ≤ N)
- 2 x y: Updates the x-th element of the array to y (1 ≤ x ≤ N, -1,000,000,000 ≤ y ≤ 1,000,000,000)
Implementation of Segment Tree
Now we will implement a segment tree in C# to solve the above problem.
using System;
class SegmentTree
{
private int[] tree;
private int size;
public SegmentTree(int n)
{
size = n;
tree = new int[n * 4]; // Size of the segment tree
}
// Build the tree
public void Build(int[] arr, int node, int start, int end)
{
if (start == end)
{
tree[node] = arr[start]; // Leaf node
}
else
{
int mid = (start + end) / 2;
Build(arr, node * 2, start, mid); // Left child
Build(arr, node * 2 + 1, mid + 1, end); // Right child
tree[node] = tree[node * 2] + tree[node * 2 + 1]; // Update parent node
}
}
// Range sum query
public int Query(int node, int start, int end, int l, int r)
{
if (r < start || end < l)
{
return 0; // Range not evaluable
}
if (l <= start && end <= r)
{
return tree[node]; // Completely inside
}
int mid = (start + end) / 2;
int leftSum = Query(node * 2, start, mid, l, r);
int rightSum = Query(node * 2 + 1, mid + 1, end, l, r);
return leftSum + rightSum; // Return sum of both ranges
}
// Update
public void Update(int node, int start, int end, int idx, int val)
{
if (start == end)
{
tree[node] = val; // Update leaf node
}
else
{
int mid = (start + end) / 2;
if (start <= idx && idx <= mid)
{
Update(node * 2, start, mid, idx, val); // Update left child
}
else
{
Update(node * 2 + 1, mid + 1, end, idx, val); // Update right child
}
tree[node] = tree[node * 2] + tree[node * 2 + 1]; // Update parent node
}
}
}
class Program
{
static void Main(string[] args)
{
int N, M;
N = int.Parse(Console.ReadLine());
M = int.Parse(Console.ReadLine());
int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
SegmentTree segTree = new SegmentTree(N);
segTree.Build(arr, 1, 0, N - 1); // Build segment tree
for (int i = 0; i < M; i++)
{
string[] query = Console.ReadLine().Split(' ');
int type = int.Parse(query[0]);
if (type == 1)
{
// Range sum query
int l = int.Parse(query[1]) - 1;
int r = int.Parse(query[2]) - 1;
Console.WriteLine(segTree.Query(1, 0, N - 1, l, r));
}
else if (type == 2)
{
// Update
int x = int.Parse(query[1]) - 1;
int y = int.Parse(query[2]);
segTree.Update(1, 0, N - 1, x, y);
}
}
}
}
Code Explanation
The above C# code represents the implementation of a segment tree to solve the given problem.
The explanation for each method and class is as follows:
Class and Variable Explanation
SegmentTree: A class representing the segment tree. It takes an array to build the tree and handles range sum queries and updates.tree: An array representing the segment tree. The maximum size of the array isN * 4.Build: A method that constructs the segment tree from the given array.Query: A method that returns the sum for a given interval.Update: A method that updates the value at a given index and reflects changes in the tree.
Main Function Explanation
The main function takes the size of the array and the number of queries as input, builds the segment tree with the given array, and then, based on the queries,
computes the range sum or performs updates.
Conclusion
In this article, we explored the implementation of a segment tree using C# and how to solve range sum query and update problems.
The segment tree is a powerful tool for efficiently handling interval queries and can be applied to various problems.
When faced with problems requiring complex queries or updates, it is advisable to consider using a segment tree.
I hope you deepen your understanding of this data structure by solving various practice problems.