Welcome to the segment trees section of the lesson!

Segment trees are a powerful data structure used to efficiently handle range-based queries on arrays. They enable us to perform various operations such as finding the sum, minimum, maximum, or applying updates to a range of elements in an array.

To build a segment tree, we divide the array into smaller segments and calculate the required metric (e.g., sum) for each segment. These metrics are then combined to form the final tree structure, where each node represents a segment of the array.

Here's an example of building a segment tree for an array [1, 2, 3, 4, 5]:

1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6// Function to build the segment tree
7void buildSegmentTree(vector<int>& tree, vector<int>& arr, int start, int end, int treeNode) {
8    if (start == end) {
9        tree[treeNode] = arr[start];
10        return;
11    }
12
13    int mid = (start + end) / 2;
14
15    buildSegmentTree(tree, arr, start, mid, 2 * treeNode);
16    buildSegmentTree(tree, arr, mid + 1, end, 2 * treeNode + 1);
17
18    tree[treeNode] = tree[2 * treeNode] + tree[2 * treeNode + 1];
19}
20
21int main() {
22    vector<int> arr = {1, 2, 3, 4, 5};
23    int n = arr.size();
24
25    // Height of the segment tree
26    int treeHeight = (int)(ceil(log2(n)));
27    int treeSize = 2 * (int)pow(2, treeHeight) - 1;
28
29    // Create an empty segment tree
30    vector<int> tree(treeSize);
31
32    // Build the segment tree
33    buildSegmentTree(tree, arr, 0, n - 1, 1);
34
35    // Print the segment tree
36    for (int i = 1; i < treeSize; i++) {
37        cout << tree[i] << " ";
38    }
39    cout << endl;
40
41    return 0;
42}

In the above example, we define a function buildSegmentTree that recursively builds the segment tree. The tree is built by dividing the array into smaller segments until we reach the base case where the segment represents a single element. The tree is then constructed by combining the metrics of the child segments.

Feel free to run the code to see the segment tree for the given array.

Segment trees have various applications, including finding the sum of elements in a given range, updating values in a range of elements, and finding the minimum or maximum element in a range. They are particularly useful in scenarios where range-based queries are frequently performed.

Now that you have an overview of segment trees, let's dive deeper into their implementation and explore more advanced operations and optimizations!

xxxxxxxxxx

}

#include <iostream>

#include <vector>

​

using namespace std;

​

// Function to build the segment tree

void buildSegmentTree(vector<int>& tree, vector<int>& arr, int start, int end, int treeNode) {

    if (start == end) {

        tree[treeNode] = arr[start];

        return;

    }

​

    int mid = (start + end) / 2;

​

    buildSegmentTree(tree, arr, start, mid, 2 * treeNode);

    buildSegmentTree(tree, arr, mid + 1, end, 2 * treeNode + 1);

​

    tree[treeNode] = tree[2 * treeNode] + tree[2 * treeNode + 1];

}

​

int main() {

    vector<int> arr = {1, 2, 3, 4, 5};

    int n = arr.size();

​

    // Height of the segment tree

    int treeHeight = (int)(ceil(log2(n)));

    int treeSize = 2 * (int)pow(2, treeHeight) - 1;

​

    // Create an empty segment tree