🌲 Segment Trees – Complete In-Depth Explanation

A Segment Tree is a powerful data structure used for efficiently handling range queries on an array. It allows you to perform operations like finding the sum, minimum, maximum, greatest common divisor (GCD), or any other associative operation on a subarray (segment) of the original array in logarithmic time. This makes it significantly faster than iterating through the array for each query.

📌 Why are Segment Trees Important?

🚀 **Efficient Range Queries:** O(log n) time complexity for queries.
⚙️ **Supports Various Operations:** Sum, min, max, GCD, product, etc.
💡 **Useful for Dynamic Updates:** Can be adapted to handle updates to the array elements.
🛠️ **Foundation for Advanced Data Structures:** Used as a building block in more complex data structures.

📌 Understanding Segment Trees with an Example

Let's consider an array: `[2, 5, 1, 4, 9, 3, 7]`

A segment tree for this array is a binary tree where:

Each node represents a segment (subarray) of the original array.
The root node represents the entire array.
The leaf nodes represent individual elements of the array.
Internal nodes store the result of the operation (e.g., sum) for the segment they represent, calculated from their children.

Here's a conceptual representation of a segment tree for the above array, calculating the sum:


                                    [27]  (0, 6)  Sum of all elements
                                   /      \
                              [8]  (0, 2)       [19] (3, 6)
                             /   \         /   \
                          [7]  (0, 1)    [1] (2, 2)   [12] (3, 5)   [7] (6, 6)
                         / \         /        /  \
                       [2](0,0) [5](1,1) [1](2,2) [4](3,3) [9](4,4)  [3](5,5) [7](6,6)

The tuples (start, end) next to each node indicate the range it covers.

🔹 Key Points

**Hierarchical Structure:** Represents the array in a hierarchical manner.
**Overlapping Segments:** Segments can overlap, allowing efficient range queries.
**Balanced Tree:** Typically a balanced binary tree, ensuring logarithmic time complexity.

🛠 Solution Approach

The core operations on a segment tree are:

📌 1. Building the Segment Tree

The segment tree is built recursively, starting from the root node. Each internal node's value is computed from its children.

📌 2. Querying the Segment Tree

To query a range, we traverse the tree. We efficiently navigate to the nodes that cover the query range.

📌 3. Updating the Segment Tree (Optional)

If the array elements can be updated, the segment tree can be updated accordingly. This usually involves updating the leaf nodes and propagating the changes up the tree.


                  #include 
                  #include 
                  #include 
              
                  using namespace std;
              
                  vector segmentTree; // 1-based indexing for simplicity
                  int n;
              
                  void buildSegmentTree(vector& arr, int index, int low, int high) {
                      if (low == high) {
                          segmentTree[index] = arr[low];
                          return;
                      }
              
                      int mid = (low + high) / 2;
                      buildSegmentTree(arr, 2 * index, low, mid);       // Left child
                      buildSegmentTree(arr, 2 * index + 1, mid + 1, high); // Right child
                      segmentTree[index] = segmentTree[2 * index] + segmentTree[2 * index + 1];
                  }
              
                  int querySegmentTree(int index, int low, int high, int qLow, int qHigh) {
                      // Complete overlap
                      if (qLow <= low && qHigh >= high) {
                          return segmentTree[index];
                      }
              
                      // No overlap
                      if (qLow > high || qHigh < low) {
                          return 0;
                      }
              
                      // Partial overlap
                      int mid = (low + high) / 2;
                      int left = querySegmentTree(2 * index, low, mid, qLow, qHigh);
                      int right = querySegmentTree(2 * index + 1, mid + 1, high, qLow, qHigh);
                      return left + right;
                  }
              
              
                   void updateSegmentTree(int index, int low, int high, int updateIndex, int newValue) {
                      if (low == high) { // Found the leaf node
                          segmentTree[index] = newValue;
                          return;
                      }
              
                      int mid = (low + high) / 2;
                      if (updateIndex <= mid) {
                          updateSegmentTree(2 * index, low, mid, updateIndex, newValue);
                      } else {
                          updateSegmentTree(2 * index + 1, mid + 1, high, updateIndex, newValue);
                      }
              
                      segmentTree[index] = segmentTree[2 * index] + segmentTree[2 * index + 1]; // Update the parent node
                  }
              
              
                  int main() {
                      vector arr = {2, 5, 1, 4, 9, 3, 7};
                      n = arr.size();
                      segmentTree.resize(4 * n + 1); // Segment tree size can be up to 4*n + 1 (worst case)
              
                      buildSegmentTree(arr, 1, 0, n - 1); // Build the tree
              
                      // Example query: Sum from index 1 to 4 (inclusive)
                      int result = querySegmentTree(1, 0, n - 1, 1, 4);
                      cout << "Sum from index 1 to 4: " << result << endl; // Output: 19
              
                      // Example update: Change the value at index 2 to 10
                      updateSegmentTree(1, 0, n - 1, 2, 10);
              
                      // Query again after the update
                      result = querySegmentTree(1, 0, n - 1, 1, 4);
                      cout << "Sum from index 1 to 4 (after update): " << result << endl; // Output: 28
              
                      return 0;
                  }