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

Complexity Analysis

• Time Complexity:

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

• Space Complexity:

  • The space complexity of the Segment Tree is O(n) 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.

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 O(\log n) time, making it highly efficient compared to a naive approach that takes O(n) 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

Complexity Analysis

• Time Complexity:

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

• Space Complexity:

  • The space complexity of the Segment Tree is O(n) 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 O(\log n) 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

Complexity Analysis

• Time Complexity:

  • Update Operation: Updating an element in the Segment Tree also takes O(\log n) 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 O(n) 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.

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