Java Coding Test Course, Segment Tree

Hello! In this article, we will learn about the Segment Tree, which is one of the algorithms that can be useful in coding tests using Java. The segment tree is primarily used to efficiently handle range queries and range updates. In this article, I will explain the basic concept of segment trees, example problems related to it, and the detailed process of solving those problems.

What is a Segment Tree?

A segment tree is a data structure used to store information about a specific range in an array and to process queries efficiently. It mainly supports the following operations:

Calculating the sum of a specified range
Updating the value at a specified position
Finding the minimum and maximum values in a range

A segment tree can process queries in O(log n) time with a space complexity of O(n). This allows for effective handling of large-scale data.

Problem Introduction

Now, let’s solve a problem using the ‘Segment Tree.’

Problem Description

Given an array of integers, write a program that provides two functions: to find the sum of a specific range and to update the value at a specific index.

The functionalities to be implemented are as follows:

Range Sum Query: Given two indices l and r, return the sum between l and r.
Update Query: Update the value at index index to value.

Input Format

First line: size of the array n (1 ≤ n ≤ 10^5)
Second line: n integers (1 ≤ arr[i] ≤ 10^9)
Third line: number of queries q
Next q lines: the queries are one of two formats:
    1. 1 l r (range sum query)
    2. 2 index value (update query)

Output Format

Output the results of the range sum queries line by line.

Problem Solving Process

1. Implementing the Segment Tree

First, we need to implement the segment tree. The segment tree is structured to store the sums from non-leaf nodes down to the leaf nodes. We will declare an array tree for this purpose and write a method to build the tree.

java
public class SegmentTree {
    private int[] tree;
    private int n;

    public SegmentTree(int[] arr) {
        n = arr.length;
        tree = new int[n * 4];
        buildTree(arr, 0, 0, n - 1);
    }

    private void buildTree(int[] arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            buildTree(arr, node * 2 + 1, start, mid);
            buildTree(arr, node * 2 + 2, mid + 1, end);
            tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2];
        }
    }

    // Range sum query method
    public int rangeSum(int l, int r) {
        return rangeSumHelper(0, 0, n - 1, l, r);
    }

    private int rangeSumHelper(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return 0; // Query range does not overlap with node range
        }
        if (l <= start && end <= r) {
            return tree[node]; // Node range is completely within query range
        }
        int mid = (start + end) / 2;
        int leftSum = rangeSumHelper(node * 2 + 1, start, mid, l, r);
        int rightSum = rangeSumHelper(node * 2 + 2, mid + 1, end, l, r);
        return leftSum + rightSum;
    }

    // Update method
    public void update(int index, int value) {
        updateHelper(0, 0, n - 1, index, value);
    }

    private void updateHelper(int node, int start, int end, int index, int value) {
        if (start == end) {
            tree[node] = value;
        } else {
            int mid = (start + end) / 2;
            if (start <= index && index <= mid) {
                updateHelper(node * 2 + 1, start, mid, index, value);
            } else {
                updateHelper(node * 2 + 2, mid + 1, end, index, value);
            }
            tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2];
        }
    }
}

2. Main Program

Now, I will write the main program that includes the segment tree class to handle input and process queries.

java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        int[] arr = new int[n];
        
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        SegmentTree segmentTree = new SegmentTree(arr);
        
        int q = scanner.nextInt();
        for (int i = 0; i < q; i++) {
            int type = scanner.nextInt();
            if (type == 1) { // Range sum query
                int l = scanner.nextInt();
                int r = scanner.nextInt();
                System.out.println(segmentTree.rangeSum(l, r));
            } else if (type == 2) { // Update query
                int index = scanner.nextInt();
                int value = scanner.nextInt();
                segmentTree.update(index, value);
            }
        }
        
        scanner.close();
    }
}

3. Time Complexity Analysis

The time complexity of the segment tree is as follows:

Range sum query: O(log n)
Update query: O(log n)

Therefore, processing q queries with an array containing n data results in an overall time complexity of O(q log n).

Conclusion

In this tutorial, we learned about segment trees in detail. The segment tree is a powerful tool that can efficiently solve various problems and can be used in multiple fields, such as counting problems, maximum/minimum problems, etc. I hope this material helps you in your coding test preparation! If you have any additional questions, please leave a comment.