Operations on Segment Tree

We have seen the introduction to Segment Trees, how they work, and how they are stored. Now, we will learn about the essential operations on a Segment Tree. This lesson will cover the following concepts:

• Implementation of Segment Tree: Learn how to construct a Segment Tree from an array.
• Querying a Segment Tree: Understand how to perform range queries with detailed explanations and code examples.
• Updating a Segment Tree: Discover how to update elements in the Segment Tree with step-by-step guides and code.

By the end of this lesson, you will have a comprehensive understanding of how to work with Segment Trees, perform range queries, and update elements efficiently.

Implementation of Segment Tree

To construct the segment tree, we will use a recursive approach to build the tree, starting from the leaves and combining results up to the root. This approach ensures that both querying and updating operations are performed efficiently, making it ideal for large datasets.

Our approach involves dividing the array into smaller segments until each segment contains a single element. Then, we combine these segments to form the tree. This method leverages the divide and conquer strategy, making the problem more manageable and the solution more efficient.

Step-by-Step Algorithm

1. Initialization:

   • Start with an array arr of size n.
   • Create an array tree of size 4 * n to store the Segment Tree. The size 4 * n ensures there is enough space for all nodes, even in the worst case.

2. Build Tree:

   • Base Case:
     • If the segment contains only one element (i.e., start == end):
       • Store the element in the corresponding tree node.
       • tree[node] = arr[start]
   • Recursive Case:
     • Calculate the middle index mid = (start + end) / 2.
     • Recursively build the left subtree: buildTree(arr, 2 * node, start, mid, tree)
     • Recursively build the right subtree: buildTree(arr, 2 * node + 1, mid + 1, end, tree)
     • Combine the results of the left and right subtrees:
       • tree[node] = tree[2 * node] + tree[2 * node + 1]

3. Implementation Details:

   • The root node is at index 1.
   • The left child of a node at index i is at index 2i.
   • The right child of a node at index i is at index 2i + 1.

Algorithm Walkthrough

Using the array [2, 4, 6, 8, 10, 12], let's walk through the construction of the Segment Tree:

1. Initialization:

   • Array: [2, 4, 6, 8, 10, 12]
   • Tree size: 4 * 6 = 24
   • Initial tree: [null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null]

2. Build Tree:

   • Start building from the root node:
     • node 1: Segment [0, 5]
       • mid = 2
       • Build left subtree: node 2, Segment [0, 2]
         • mid = 1
         • Build left subtree: node 4, Segment [0, 1]
           • mid = 0
           • Build left subtree: node 8, Segment [0, 0]
             • Leaf node: tree[8] = arr[0] = 2
           • Build right subtree: node 9, Segment [1, 1]
             • Leaf node: tree[9] = arr[1] = 4
           • Combine: tree[4] = tree[8] + tree[9] = 2 + 4 = 6
         • Build right subtree: node 5, Segment [2, 2]
           • Leaf node: tree[5] = arr[2] = 6
         • Combine: tree[2] = tree[4] + tree[5] = 6 + 6 = 12
       • Build right subtree: node 3, Segment [3, 5]
         • mid = 4
         • Build left subtree: node 6, Segment [3, 4]
           • mid = 3
           • Build left subtree: node 12, Segment [3, 3]
             • Leaf node: tree[12] = arr[3] = 8
           • Build right subtree: node 13, Segment [4, 4]
             • Leaf node: tree[13] = arr[4] = 10
           • Combine: tree[6] = tree[12] + tree[13] = 8 + 10 = 18
         • Build right subtree: node 7, Segment [5, 5]
           • Leaf node: tree[7] = arr[5] = 12
         • Combine: tree[3] = tree[6] + tree[7] = 18 + 12 = 30
       • Combine: tree[1] = tree[2] + tree[3] = 12 + 30 = 42

Resulting tree:

[null, 42, 12, 30, 6, 6, 18, 12, 2, 4, null, null, 8, 10, null, null, null, null, null, null, null, null, null, null]

Code

public class Solution {

  // Build the segment tree
  public void buildTree(int[] arr, int node, int start, int end, int[] tree) {
    // If the segment has only one element
    if (start == end) {
      tree[node] = arr[start];
    } else {
      // Find the middle index
      int mid = (start + end) / 2;

      // Recursively build the left and right subtrees
      buildTree(arr, 2 * node, start, mid, tree);
      buildTree(arr, 2 * node + 1, mid + 1, end, tree);

      // Merge the results from the left and right subtrees
      tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
  }

  public static void main(String[] args) {
    int[] arr = { 2, 4, 6, 8, 10, 12 };

    // Initialize segment tree array with appropriate size
    int[] tree = new int[4 * arr.length];

    // Create an instance of Solution
    Solution sol = new Solution();

    // Build the segment tree. Start with index 1 to match the given example behavior.
    sol.buildTree(arr, 1, 0, arr.length - 1, tree);

    // Print the segment tree
    for (int value : tree) {
      System.out.print(value + " ");
    }
  }
}

Complexity Analysis

• Time Complexity:

  • Build Operation: The build operation takes time because it processes each element of the array exactly once.

• Space Complexity:

  • The space complexity of the Segment Tree is because we need to store the tree in an array of size . This extra space ensures that all nodes, including internal and leaf nodes, have enough space to be stored efficiently.

Querying a Segment Tree

Once the Segment Tree is built, it can be used to perform efficient range queries. A common use case for a Segment Tree is querying the sum of elements in a given range. The structure of the Segment Tree allows us to break down the query into smaller segments, quickly summing the required values. This ensures that range queries can be performed in time, making it highly efficient compared to a naive approach that takes time.

Step-by-Step Algorithm

1. Construct the Segment Tree:

   • Before performing any queries, we need to construct the Segment Tree. This process is covered in the previous section.

2. Initialization:

   • Define the query range [L, R].
   • Initialize the result to store the sum of the range.

3. Recursive Query Function:

   • Base Case:
     • If the query range [L, R] is completely outside the segment range [start, end] of the current node, return 0.
     • This step ensures that non-overlapping segments do not contribute to the sum.
   • Complete Overlap:
     • If the segment range [start, end] is completely within the query range [L, R], return the value stored in the current node.
     • This step helps in quickly summing up the segments that are fully covered by the query range.
   • Partial Overlap:
     • If there is a partial overlap between the segment range [start, end] and the query range [L, R], split the range further:
       • Calculate the middle index mid = (start + end) / 2.
       • Recursively query the left child: leftSum = query(2 * node, start, mid, L, R, tree).
       • Recursively query the right child: rightSum = query(2 * node + 1, mid + 1, end, L, R, tree).
       • Combine the results of the left and right children to get the final sum for the query range: result = leftSum + rightSum.

4. Combine Results:

   • Sum the results obtained from the left and right child queries to get the final result for the range [L, R].

Algorithm Walkthrough

Using the input [2, 4, 6, 8, 10, 12].

Using the Segment Tree from the previous section [0, 42, 12, 30, 6, 6, 18, 12, 2, 4, 0, 0, 8, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], let's query the sum of elements in the range [1, 4]:

1. Initialization:

   • Query range: [1, 4]
   • Result: 0

2. Recursive Query:

   • Start with the root node 1 (segment [0, 5]):
     • Partial Overlap:
       • The query range [1, 4] partially overlaps with the segment [0, 5].
       • Calculate the middle index: mid = 2
     • Query Left Child:
       • Move to left child node 2 (segment [0, 2]):
         • Partial Overlap:
           • The query range [1, 4] partially overlaps with the segment [0, 2].
           • Calculate the middle index: mid = 1
         • Query Left Child:
           • Move to left child node 4 (segment [0, 1]):
             • Partial Overlap:
               • The query range [1, 4] partially overlaps with the segment [0, 1].
               • Calculate the middle index: mid = 0
             • Query Left Child:
               • Move to left child node 8 (segment [0, 0]):
                 • No Overlap:
                   • The query range [1, 4] does not overlap with the segment [0, 0].
                   • Return 0
             • Query Right Child:
               • Move to right child node 9 (segment [1, 1]):
                 • Complete Overlap:
                   • The query range [1, 4] completely overlaps with the segment [1, 1].
                   • Return 4
             • Combine Results:
               • Combine the results of the left and right children: 0 + 4 = 4
           • Return 4 to node 4
         • Query Right Child:
           • Move to right child node 5 (segment [2, 2]):
             • Complete Overlap:
               • The query range [1, 4] completely overlaps with the segment [2, 2].
               • Return 6
         • Combine Results:
           • Combine the results of the left and right children: 4 + 6 = 10
       • Return 10 to node 2
     • Query Right Child:
       • Move to right child node 3 (segment [3, 5]):
         • Partial Overlap:
           • The query range [1, 4] partially overlaps with the segment [3, 5].
           • Calculate the middle index: mid = 4
         • Query Left Child:
           • Move to left child node 6 (segment [3, 4]):
             • Complete Overlap:
               • The query range [1, 4] completely overlaps with the segment [3, 4].
               • Return 18
         • Query Right Child:
           • Move to right child node 7 (segment [5, 5]):
             • No Overlap:
               • The query range [1, 4] does not overlap with the segment [5, 5].
               • Return 0
         • Combine Results:
           • Combine the results of the left and right children: 18 + 0 = 18
       • Return 18 to node 3
     • Combine Results:
       • Combine the results of the left and right children: 10 + 18 = 28

Result:

• The sum of elements in the range [1, 4] is 28.

Code

public class Solution {

  // Array to store the segment tree
  int[] tree;
  int[] arr;
  int n;

  // Build the segment tree
  public void buildTree(int[] arr, int node, int start, int end, int[] tree) {
    // If the segment has only one element
    if (start == end) {
      // Assign the value to the corresponding leaf node in the tree
      tree[node] = arr[start];
    } else {
      // Find the middle index
      int mid = (start + end) / 2;

      // Recursively build the left and right subtree
      buildTree(arr, 2 * node, start, mid, tree);
      buildTree(arr, 2 * node + 1, mid + 1, end, tree);

      // Merge the results from the left and right subtrees
      tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
  }

  public int query(int node, int start, int end, int L, int R, int[] tree) {
    // If the query range is outside the segment range
    if (R < start || L > end) {
      return 0; // Return 0 as it does not overlap
    }

    // If the segment is fully within the query range
    if (L <= start && end <= R) {
      return tree[node]; // Return the value stored in the current segment
    }

    // Find the middle index
    int mid = (start + end) / 2;

    // Recursively query the left subtree
    int leftSum = query(2 * node, start, mid, L, R, tree);

    // Recursively query the right subtree
    int rightSum = query(2 * node + 1, mid + 1, end, L, R, tree);

    // Return the sum of both subtrees
    return leftSum + rightSum;
  }

  public static void main(String[] args) {
    int[] arr = { 2, 4, 6, 8, 10, 12 };
    int n = arr.length;
    int[] tree = new int[4 * n];
    Solution sol = new Solution();

    sol.arr = arr;
    sol.n = n;
    sol.tree = tree;

    sol.buildTree(arr, 1, 0, n - 1, tree);
    int result = sol.query(1, 0, n - 1, 1, 4, tree);
    System.out.println(result);
  }
}

Complexity Analysis

• Time Complexity:

  • Query Operation: Querying a range in the Segment Tree takes time. This is because the maximum number of nodes we need to visit is proportional to the height of the tree, which is

• Space Complexity:

  • The space complexity of the Segment Tree is because we need to store the tree in an array of size (4 * n). This extra space ensures that all nodes, including internal and leaf nodes, have enough space to be stored efficiently.

Updating a Segment Tree

Updating a Segment Tree involves changing the value of an element in the original array and then updating the corresponding nodes in the tree to reflect this change. This ensures that the Segment Tree remains accurate for subsequent queries. The update operation is efficient, taking time, as it only affects the nodes along the path from the updated element to the root.

Step-by-Step Algorithm for Updating a Segment Tree

1. Initialization:

   • Identify the index idx of the element to be updated in the array.
   • Determine the new value val to be updated at this index.

2. Recursive Update Function:

   • Base Case:
     • If the current segment [start, end] corresponds to the single element to be updated (start == end):
       • Update the value at the corresponding leaf node in the tree: tree[node] = val.
   • Recursive Case:
     • Calculate the middle index mid = (start + end) / 2.
     • Update Left Subtree:
       • If idx lies within the left segment [start, mid], recursively update the left child: update(2 * node, start, mid, idx, val, tree).
     • Else Update Right Subtree:
       • If idx lies within the right segment [mid + 1, end], recursively update the right child: update(2 * node + 1, mid + 1, end, idx, val, tree).
     • Combine Results:
       • After updating the relevant child, update the current node to reflect the changes: tree[node] = tree[2 * node] + tree[2 * node + 1].

Algorithm Walkthrough

Using the input [2, 4, 6, 8, 10, 12]. let's update the element at index 2 to 7: Using the Segment Tree from the previous section [0, 42, 12, 30, 6, 6, 18, 12, 2, 4, 0, 0, 8, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].

1. Initialization:

   • Update index: 2
   • New value: 7

2. Recursive Update:

   • Start with the root node 1 (segment [0, 5]):

     • Since the update index 2 lies within the segment [0, 5], we need to continue updating the children.
     • Calculate the middle index: mid = (start + end) / 2 = (0 + 5) / 2 = 2.

   • Update Left Child:

     • Move to the left child node 2 (segment [0, 2]):

       • The update index 2 lies within the segment [0, 2], so we need to update this segment further.
       • Calculate the middle index: mid = (start + end) / 2 = (0 + 2) / 2 = 1.

     • Update Right Child of Node 2:

       • Move to the right child node 5 (segment [2, 2]):
         • This is a leaf node where start equals end and it matches the update index 2.
         • Base Case:
           • Update the value at the corresponding leaf node: tree[5] = 7.

     • Combine Results:

       • After updating the leaf node, move back to the parent node 2 and update its value to reflect the change:
       • tree[2] = tree[4] + tree[5] = 6 + 7 = 13.

   • Update Root Node:

     • Finally, move back to the root node 1 and update its value to reflect the change:
     • tree[1] = tree[2] + tree[3] = 13 + 30 = 43.

Resulting tree:

[0, 43, 13, 30, 6, 7, 18, 12, 2, 4, 0, 0, 8, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Code

public class Solution {

  // Array to store the segment tree
  int[] tree;
  int[] arr;
  int n;

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

  // Query the segment tree for range sum
  public int query(int node, int start, int end, int L, int R, int[] tree) {
    if (R < start || L > end) {
      return 0;
    }
    if (L <= start && end <= R) {
      return tree[node];
    }
    int mid = (start + end) / 2;
    int leftSum = query(2 * node, start, mid, L, R, tree);
    int rightSum = query(2 * node + 1, mid + 1, end, L, R, tree);
    return leftSum + rightSum;
  }

  // Update the segment tree with a new value at a specific index
  public void update(
    int node,
    int start,
    int end,
    int idx,
    int val,
    int[] tree
  ) {
    // If the segment has only one element
    if (start == end) {
      // Assign the new value to the corresponding leaf node in the tree
      tree[node] = val;
    } else {
      // Find the middle index
      int mid = (start + end) / 2;

      // Recursively update the left or right subtree based on the index
      if (start <= idx && idx <= mid) {
        update(2 * node, start, mid, idx, val, tree);
      } else {
        update(2 * node + 1, mid + 1, end, idx, val, tree);
      }

      // Merge the results from the left and right subtrees
      tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
  }

  public static void main(String[] args) {
    int[] arr = { 2, 4, 6, 8, 10, 12 };
    int n = arr.length;
    int[] tree = new int[4 * n];
    Solution sol = new Solution();

    sol.arr = arr;
    sol.n = n;
    sol.tree = tree;

    // Build the segment tree. Start with index 1 to match the given example behavior.
    sol.buildTree(arr, 1, 0, n - 1, tree);

    // Query the segment tree for range sum
    int result = sol.query(1, 0, n - 1, 1, 4, tree);
    System.out.println(result); // Output should be 28

    // Update the segment tree
    sol.update(1, 0, n - 1, 2, 7, tree);
    result = sol.query(1, 0, n - 1, 1, 4, tree);
    System.out.println(result); // Output should be 29
  }
}

Complexity Analysis

• Time Complexity:

  • Update Operation: Updating an element in the Segment Tree also takes time. This is because the update operation only affects the nodes along the path from the updated element to the root, which is proportional to the height of the tree.

• Space Complexity:

  • The space complexity of the Segment Tree is because we need to store the tree in an array of size . This extra space ensures that all nodes, including internal and leaf nodes, have enough space to be stored efficiently.

Now, let's start solving the problem on segment tree.

I just read a lesson on **Operations on Segment Tree** (DSA) and want to truly understand it. Explain Operations on Segment Tree from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Operations on Segment Tree** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Operations on Segment Tree** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Operations on Segment Tree** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.