Range Query using Segment Trees in C#

General
1

Let’s tackle a common problem that can be efficiently solved using a segment tree: the Range Minimum Query (RMQ). In this problem, we want to quickly find the minimum value in a specified range of an array and also be able to update elements in the array.

Problem Statement

Given an array of integers, you need to:

  1. Perform a minimum query over a range [l, r].
  2. Update the value of an element at a specific index.

Example

Let’s consider an example with an array:

arr = [7, 2, 4, 1, 3, 6]

  • Query: Find the minimum value in the range from index 1 to 4, which should return 1.
  • Update: Set the value at index 2 to 0, making the array [7, 2, 0, 1, 3, 6].
  • Query: Now, find the minimum from index 1 to 4, which should return 0.

Segment Tree Implementation in C#

Here’s a simple implementation of the segment tree for the Range Minimum Query problem in C#:

using System;

class SegmentTree
{
    private int[] tree;
    private int[] arr;
    private int n;

    public SegmentTree(int[] input)
    {
        arr = input;
        n = input.Length;
        tree = new int[4 * n]; // Size of segment tree
        BuildTree(0, 0, n - 1);
    }

    private void BuildTree(int node, int start, int end)
    {
        if (start == end)
        {
            tree[node] = arr[start];
        }
        else
        {
            int mid = (start + end) / 2;
            BuildTree(2 * node + 1, start, mid);
            BuildTree(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)
    {
        UpdateTree(0, 0, n - 1, idx, value);
    }

    private void UpdateTree(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 (idx <= mid)
            {
                UpdateTree(2 * node + 1, start, mid, idx, value);
            }
            else
            {
                UpdateTree(2 * node + 2, mid + 1, end, idx, value);
            }
            tree[node] = Math.Min(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

    public int RangeMin(int l, int r)
    {
        return RangeMinQuery(0, 0, n - 1, l, r);
    }

    private int RangeMinQuery(int node, int start, int end, int l, int r)
    {
        if (r < start || end < l)
        {
            return int.MaxValue; // Out of range
        }
        if (l <= start && end <= r)
        {
            return tree[node]; // Fully in range
        }

        int mid = (start + end) / 2;
        int leftMin = RangeMinQuery(2 * node + 1, start, mid, l, r);
        int rightMin = RangeMinQuery(2 * node + 2, mid + 1, end, l, r);
        return Math.Min(leftMin, rightMin);
    }
}

class Program
{
    static void Main(string[] args)
    {
        int[] input = { 7, 2, 4, 1, 3, 6 };
        SegmentTree segTree = new SegmentTree(input);

        Console.WriteLine("Minimum of range (1, 4): " + segTree.RangeMin(1, 4)); // Outputs 1

        segTree.Update(2, 0); // Update index 2 to value 0
        Console.WriteLine("Minimum of range (1, 4) after update: " + segTree.RangeMin(1, 4)); // Outputs 0
    }
}

Explanation

  1. Building the Segment Tree: The BuildTree method constructs the segment tree based on the input array. Each node in the tree stores the minimum value for a specific segment of the array.

  2. Updating Values: The UpdateTree method updates a specific index in the array and adjusts the segment tree accordingly to reflect the new value.

  3. Range Minimum Query: The RangeMinQuery method computes the minimum value for a given range by recursively checking whether the current segment is completely within, outside, or partially overlapping the query range.

Complexity

  • Time Complexity: Both update and range minimum queries operate in (O(\log n)).
  • Space Complexity: The space complexity is (O(n)) due to the storage of the segment tree.

This implementation allows for efficient querying and updating, making it suitable for scenarios where these operations are needed frequently.