Segment Tree Construction 🎯

Segment Trees are a data structure used for efficiently handling range queries and updates in an array. They are particularly useful in algorithms that require frequent range queries or updates.

Understanding Segment Trees 📝

A segment tree is a data structure that divides an array into smaller segments, where each segment represents a sub-array of the original array. It stores the cumulative sum or other aggregates of these segments, allowing for efficient range queries and updates.

Key Points 💡

Segment trees help solve problems more efficiently by reducing the number of operations required.
They can handle range queries (finding the sum or any aggregate function over a range) and range updates (updating values within a range) in logarithmic time, which is a significant improvement over linear time for some problems.

Building a Segment Tree 💡

To build a segment tree, we first build a binary tree where each node represents a segment of the original array. The construction process involves calculating and storing cumulative sums (or other aggregates) for each segment.

Step-by-Step Guide 📝

Create an empty segment tree with a single root node.
Populate the tree by recursively constructing left and right sub-trees for each non-leaf node, using the left and right halves of the original array.
Calculate and store the cumulative sum (or other aggregate) for each segment in the tree.

Segment Tree Example 💡

Let's construct a segment tree for the following array:

[3, 7, 4, 6, 5, 9, 2, 10, 1]

Here's the code for building a segment tree with cumulative sums:

python

def build_segment_tree(arr, start, end, tree, idx):
    if start == end:
        tree[idx] = arr[start]
        return tree[idx]

    mid = (start + end) // 2
    left_val = build_segment_tree(arr, start, mid, tree, 2 * idx + 1)
    right_val = build_segment_tree(arr, mid + 1, end, tree, 2 * idx + 2)

    tree[idx] = left_val + right_val
    return tree[idx]

arr = [3, 7, 4, 6, 5, 9, 2, 10, 1]
n = len(arr)
tree = [0] * (4 * n)
build_segment_tree(arr, 0, n - 1, tree, 0)

Now, the tree array contains the segment tree for the original array.

Segment Tree Queries and Updates 💡

With the segment tree built, we can perform range queries and updates efficiently.

Range Query 💡

To find the sum of a range, we traverse the segment tree from the root node down to the leaf nodes corresponding to the given range, and sum the values of the visited nodes.

Here's the code for performing a range query:

python

def range_query(tree, start, end, qstart, qend, tree_idx, cumulative_sum):
    if qstart <= start and end <= qend:
        return tree[tree_idx]

    if end < qstart or qend < start:
        return 0

    mid = (start + end) // 2
    left_val = range_query(tree, start, mid, qstart, qend, 2 * tree_idx + 1, cumulative_sum)
    right_val = range_query(tree, mid + 1, end, qstart, qend, 2 * tree_idx + 2, cumulative_sum)
    return left_val + right_val

Range Update 💡

To update a range, we first find the leaf nodes corresponding to the given range, then update their values in the original array and recursively update the parent nodes in the segment tree.

Here's the code for performing a range update:

python

def range_update(tree, start, end, qstart, qend, value, tree_idx, cumulative_sum):
    if qstart <= start and end <= qend:
        cumulative_sum[start] += value
        update_segment_tree(tree, start, start, tree_idx, cumulative_sum)
        return

    if end < qstart or qend < start:
        return

    mid = (start + end) // 2
    if qstart <= mid:
        update_segment_tree(tree, start, mid, 2 * tree_idx + 1, cumulative_sum)
    if qend > mid:
        update_segment_tree(tree, mid + 1, end, 2 * tree_idx + 2, cumulative_sum)

def update_segment_tree(tree, start, end, tree_idx, cumulative_sum):
    if start == end:
        return

    mid = (start + end) // 2
    left_val = tree[2 * tree_idx + 1]
    right_val = tree[2 * tree_idx + 2]
    tree[tree_idx] = left_val + right_val
    tree[tree_idx] = cumulative_sum[mid] + tree[tree_idx]

    if left_val == right_val:
        return

    tree[2 * tree_idx + 1] = cumulative_sum[mid]
    update_segment_tree(tree, start, mid, 2 * tree_idx + 1, cumulative_sum)
    update_segment_tree(tree, mid + 1, end, 2 * tree_idx + 2, cumulative_sum)

Segment Tree Construction 🎯

Segment Tree Construction 🎯

Understanding Segment Trees 📝

Key Points 💡

Building a Segment Tree 💡

Step-by-Step Guide 📝

Segment Tree Example 💡

Segment Tree Queries and Updates 💡

Range Query 💡

Range Update 💡

Segment Tree Quiz 🎯