1. Introduction

The Segment Tree is a versatile data structure that allows for fast query and update operations on a range of elements within an array. Typically, segment trees are used for range-based queries, such as finding the sum, minimum, or maximum of numbers in a range. This post will demonstrate the implementation of a segment tree that supports range sum queries and point updates.

2. Program Steps

1. Initialize the segment tree with a given array.

2. Build the segment tree recursively.

3. Implement a query function to get the sum of a range.

4. Implement an update function to update an element in the array and its corresponding values in the segment tree.

3. Code Program

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

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

    private void build(int[] arr, int l, int r, int index) {
        if (l == r) {
            tree[index] = arr[l];
            return;
        }
        int mid = (l + r) / 2;
        build(arr, l, mid, 2 * index + 1);
        build(arr, mid + 1, r, 2 * index + 2);
        tree[index] = tree[2 * index + 1] + tree[2 * index + 2];
    }

    public int query(int l, int r) {
        return queryUtil(0, n - 1, l, r, 0);
    }

    private int queryUtil(int treeL, int treeR, int l, int r, int index) {
        if (l <= treeL && r >= treeR) return tree[index];
        if (r < treeL || l > treeR) return 0;
        int mid = (treeL + treeR) / 2;
        return queryUtil(treeL, mid, l, r, 2 * index + 1) + queryUtil(mid + 1, treeR, l, r, 2 * index + 2);
    }

    public void update(int idx, int value) {
        updateUtil(0, n - 1, idx, value, 0);
    }

    private void updateUtil(int l, int r, int idx, int value, int index) {
        if (l == r) {
            tree[index] = value;
            return;
        }
        int mid = (l + r) / 2;
        if (idx <= mid) updateUtil(l, mid, idx, value, 2 * index + 1);
        else updateUtil(mid + 1, r, idx, value, 2 * index + 2);
        tree[index] = tree[2 * index + 1] + tree[2 * index + 2];
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        SegmentTree st = new SegmentTree(arr);

        System.out.println(st.query(1, 3));  // Sum from index 1 to 3
        st.update(1, 10);  // Update index 1 to 10
        System.out.println(st.query(1, 3));  // Sum from index 1 to 3 after update
    }
}

Output:

15
22

4. Step By Step Explanation

1. The SegmentTree class initializes with an array and internally builds the tree representation of it.

2. The build method initializes the segment tree recursively. At each node, it divides the array segment into two halves and processes them.

3. The query method retrieves the sum for a specified range. The queryUtil function does the heavy lifting by comparing the desired range with the range represented by each node in the tree.

4. The update method allows us to change a value in the initial array and updates the segment tree accordingly. The updateUtil function performs the actual update.

5. In the main method, we create a SegmentTree from a sample array, make a sum query, then update an element, and make another sum query to see the updated results.