Given an array arr[0 . . . n-1]. The task is to perform the following operation:
- Find the maximum of elements from index l to r where 0 <= l <= r <= n-1.
- Change value of a specified element of the array to a new value x. Given i and x, change A[i] to x, 0 <= i <= n-1.
Examples:
Input: a[] = {2, 6, 7, 5, 18, 86, 54, 2}
Query1: maximum(2, 7)
Query2: update(3, 90)
Query3: maximum(2, 6)Output:
Maximum in range 2 to 7 is 86.
Maximum in range 2 to 6 is 90.
We have discussed Recursive segment tree implementation. In this post, iterative implementation is discussed.
The iterative version of the segment tree basically uses the fact, that for an index i, left child = 2 * i and right child = 2 * i + 1 in the tree. The parent for an index i in the segment tree array can be found by parent = i / 2. Thus we can easily travel up and down through the levels of the tree one by one. At first we compute the maximum in the ranges while constructing the tree starting from the leaf nodes and climbing up through the levels one by one. We use the same concept while processing the queries for finding the maximum in a range.
Since there are (log n) levels in the worst case, so querying takes log n time. For update of a particular index to a given value we start updating the segment tree starting from the leaf nodes and update all those nodes which are affected by the updation of the current node by gradually moving up through the levels at every iteration. Updation also takes log n time because there we have to update all the levels starting from the leaf node where we update the exact value at the exact index given by the user.
Below is the implementation of the above approach.
C++
// C++ Program to implement// iterative segment tree.#include <bits/stdc++.h>using namespace std;void construct_segment_tree(vector<int>& segtree, vector<int>& a, int n){ // assign values to leaves of the segment tree for (int i = 0; i < n; i++) segtree[n + i] = a[i]; /* assign values to internal nodes to compute maximum in a given range */ for (int i = n - 1; i >= 1; i--) segtree[i] = max(segtree[2 * i], segtree[2 * i + 1]);}void update(vector<int>& segtree, int pos, int value, int n){ // change the index to leaf node first pos += n; // update the value at the leaf node // at the exact index segtree[pos] = value; while (pos > 1) { // move up one level at a time in the tree pos >>= 1; // update the values in the nodes in // the next higher level segtree[pos] = max(segtree[2 * pos], segtree[2 * pos + 1]); }}int range_query(vector<int>& segtree, int left, int right, int n){ /* Basically the left and right indices will move towards right and left respectively and with every each next higher level and compute the maximum at each height. */ // change the index to leaf node first left += n; right += n; // initialize maximum to a very low value int ma = INT_MIN; while (left < right) { // if left index in odd if (left & 1) { ma = max(ma, segtree[left]); // make left index even left++; } // if right index in odd if (right & 1) { // make right index even right--; ma = max(ma, segtree[right]); } // move to the next higher level left /= 2; right /= 2; } return ma;}// Driver codeint main(){ vector<int> a = { 2, 6, 10, 4, 7, 28, 9, 11, 6, 33 }; int n = a.size(); /* Construct the segment tree by assigning the values to the internal nodes*/ vector<int> segtree(2 * n); construct_segment_tree(segtree, a, n); // compute maximum in the range left to right int left = 1, right = 5; cout << "Maximum in range " << left << " to " << right << " is " << range_query(segtree, left, right + 1, n) << "\n"; // update the value of index 5 to 32 int index = 5, value = 32; // a[5] = 32; // Contents of array : {2, 6, 10, 4, 7, 32, 9, 11, 6, 33} update(segtree, index, value, n); // compute maximum in the range left to right left = 2, right = 8; cout << "Maximum in range " << left << " to " << right << " is " << range_query(segtree, left, right + 1, n) << "\n"; return 0;} |
Java
// Java Program for the above approachimport java.util.Arrays;public class IterativeSegmentTree { private int[] segtree; private int n; public IterativeSegmentTree(int[] a) { n = a.length; segtree = new int[2 * n]; Arrays.fill(segtree, Integer.MIN_VALUE); constructSegmentTree(a); } private void constructSegmentTree(int[] a) { // assign values to leaves of the segment tree for (int i = 0; i < n; i++) { segtree[n + i] = a[i]; } /* assign values to internal nodes to compute maximum in a given range */ for (int i = n - 1; i >= 1; i--) { segtree[i] = Math.max(segtree[2 * i], segtree[2 * i + 1]); } } public void update(int pos, int value) { // change the index to leaf node first pos += n; // update the value at the leaf node // at the exact index segtree[pos] = value; while (pos > 1) { // move up one level at a time in the tree pos >>= 1; // update the values in the nodes in // the next higher level segtree[pos] = Math.max(segtree[2 * pos], segtree[2 * pos + 1]); } } public int rangeQuery(int left, int right) { /* Basically the left and right indices will move towards right and left respectively and with every each next higher level and compute the maximum at each height. */ // change the index to leaf node first left += n; right += n; // initialize maximum to a very low value int ma = Integer.MIN_VALUE; while (left < right) { // if left index in odd if ((left & 1) == 1) { ma = Math.max(ma, segtree[left]); // make left index even left++; } // if right index in odd if ((right & 1) == 1) { // make right index even right--; ma = Math.max(ma, segtree[right]); } // move to the next higher level left /= 2; right /= 2; } return ma; } //Driver code public static void main(String[] args) { int[] a = { 2, 6, 10, 4, 7, 28, 9, 11, 6, 33 }; IterativeSegmentTree tree = new IterativeSegmentTree(a); // compute maximum in the range left to right int left = 1, right = 5; System.out.println( "Maximum in range " + left + " to " + right + " is " + tree.rangeQuery(left, right + 1)); // update the value of index 5 to 32 int index = 5, value = 32; // a[5] = 32; // Contents of array : {2, 6, 10, 4, 7, 32, 9, 11, // 6, 33} tree.update(index, value); // compute maximum in the range left to right left = 2; right = 8; System.out.println( "Maximum in range " + left + " to " + right + " is " + tree.rangeQuery(left, right + 1)); }}// This code is contributed by lokeshpotta20. |
Python3
# Python Program to implement# iterative segment tree.from sys import maxsizeINT_MIN = -maxsizedef construct_segment_tree(a: list, n: int): global segtree # assign values to leaves of the segment tree for i in range(n): segtree[n + i] = a[i] # assign values to internal nodes # to compute maximum in a given range */ for i in range(n - 1, 0, -1): segtree[i] = max(segtree[2 * i], segtree[2 * i + 1])def update(pos: int, value: int, n: int): global segtree # change the index to leaf node first pos += n # update the value at the leaf node # at the exact index segtree[pos] = value while pos > 1: # move up one level at a time in the tree pos //= 2 # update the values in the nodes in # the next higher level segtree[pos] = max(segtree[2 * pos], segtree[2 * pos + 1])def range_query(left: int, right: int, n: int) -> int: global segtree # Basically the left and right indices will move # towards right and left respectively and with # every each next higher level and compute the # maximum at each height. # change the index to leaf node first left += n right += n # initialize maximum to a very low value ma = INT_MIN while left < right: # if left index in odd if left & 1: ma = max(ma, segtree[left]) # make left index even left += 1 # if right index in odd if right & 1: # make right index even right -= 1 ma = max(ma, segtree[right]) # move to the next higher level left //= 2 right //= 2 return ma# Driver Codeif __name__ == "__main__": a = [2, 6, 10, 4, 7, 28, 9, 11, 6, 33] n = len(a) # Construct the segment tree by assigning # the values to the internal nodes segtree = [0] * (2 * n) construct_segment_tree(a, n) # compute maximum in the range left to right left = 1 right = 5 print("Maximum in range %d to %d is %d" % (left, right, range_query(left, right + 1, n))) # update the value of index 5 to 32 index = 5 value = 32 # a[5] = 32; # Contents of array : {2, 6, 10, 4, 7, 32, 9, 11, 6, 33} update(index, value, n) # compute maximum in the range left to right left = 2 right = 8 print("Maximum in range %d to %d is %d" % (left, right, range_query(left, right + 1, n)))# This code is contributed by# sanjeev2552 |
C#
// C# Program for the above approachusing System;public class IterativeSegmentTree {static int[] segtree;static int n;public IterativeSegmentTree(int[] a){ n = a.Length; segtree = new int[2 * n]; for(int i=0;i<2*n;i++) { segtree[i]= Int32.MinValue; } constructSegmentTree(a);}private void constructSegmentTree(int[] a){ // assign values to leaves of the segment tree for (int i = 0; i < n; i++) { segtree[n + i] = a[i]; } /* assign values to internal nodes to compute maximum in a given range */ for (int i = n - 1; i >= 1; i--) { segtree[i] = Math.Max(segtree[2 * i], segtree[2 * i + 1]); }}public void update(int pos, int value){ // change the index to leaf node first pos += n; // update the value at the leaf node // at the exact index segtree[pos] = value; while (pos > 1) { // move up one level at a time in the tree pos >>= 1; // update the values in the nodes in // the next higher level segtree[pos] = Math.Max(segtree[2 * pos], segtree[2 * pos + 1]); }}public int rangeQuery(int left, int right){ /* Basically the left and right indices will move towards right and left respectively and with every each next higher level and compute the maximum at each height. */ // change the index to leaf node first left += n; right += n; // initialize maximum to a very low value int ma = Int32.MinValue; while (left < right) { // if left index in odd if ((left & 1) == 1) { ma = Math.Max(ma, segtree[left]); // make left index even left++; } // if right index in odd if ((right & 1) == 1) { // make right index even right--; ma = Math.Max(ma, segtree[right]); } // move to the next higher level left /= 2; right /= 2; } return ma;}//Driver codestatic public void Main (){ int[] a = { 2, 6, 10, 4, 7, 28, 9, 11, 6, 33 }; IterativeSegmentTree tree = new IterativeSegmentTree(a); // compute maximum in the range left to right int left = 1, right = 5; Console.WriteLine( "Maximum in range " + left + " to " + right + " is " + tree.rangeQuery(left, right + 1)); // update the value of index 5 to 32 int index = 5, value = 32; // a[5] = 32; // Contents of array : {2, 6, 10, 4, 7, 32, 9, 11, // 6, 33} tree.update(index, value); // compute maximum in the range left to right left = 2; right = 8; Console.WriteLine( "Maximum in range " + left + " to " + right + " is " + tree.rangeQuery(left, right + 1));}}// This code is contributed by Pushpesh Raj |
Javascript
<script>// Javascript program to implement // iterative segment tree.function construct_segment_tree(segtree, a, n){ // Assign values to leaves of the segment tree for(let i = 0; i < n; i++) segtree[n + i] = a[i]; // Assign values to internal nodes // to compute maximum in a given range for(let i = n - 1; i >= 1; i--) segtree[i] = Math.max(segtree[2 * i], segtree[2 * i + 1]);}function update(segtree, pos, value, n){ // Change the index to leaf node first pos += n; // Update the value at the leaf node // at the exact index segtree[pos] = value; while (pos > 1) { // Move up one level at a time in the tree pos >>= 1; // Update the values in the nodes in // the next higher level segtree[pos] = Math.max(segtree[2 * pos], segtree[2 * pos + 1]); }}function range_query(segtree, left, right, n){ /* Basically the left and right indices will move towards right and left respectively and with every each next higher level and compute the maximum at each height. */ // change the index to leaf node first left += n; right += n; // Initialize maximum to a very low value let ma = Number.MIN_VALUE; while (left < right) { // If left index in odd if ((left & 1) != 0) { ma = Math.max(ma, segtree[left]); // Make left index even left++; } // If right index in odd if ((right & 1) > 0) { // Make right index even right--; ma = Math.max(ma, segtree[right]); } // Move to the next higher level left = parseInt(left / 2, 10); right = parseInt(right / 2, 10); } return ma;}// Driver codelet a = [ 2, 6, 10, 4, 7, 28, 9, 11, 6, 33 ];let n = a.length;// Construct the segment tree by assigning // the values to the internal nodeslet segtree = new Array(2 * n);construct_segment_tree(segtree, a, n);// Compute maximum in the range left to rightlet left = 1, right = 5;document.write("Maximum in range " + left + " to " + right + " is " + range_query(segtree, left, right + 1, n) + "</br>");// Update the value of index 5 to 32let index = 5, value = 32;// a[5] = 32;// Contents of array : {2, 6, 10, 4, 7, 32, 9, 11, 6, 33}update(segtree, index, value, n);// Compute maximum in the range left to rightleft = 2, right = 8;document.write("Maximum in range " + left + " to " + right + " is " + range_query(segtree, left, right + 1, n) + "</br>");// This code is contributed by divyesh072019</script> |
Output
Maximum in range 1 to 5 is 28 Maximum in range 2 to 8 is 32
Complexity Analysis:
- Time Complexity: (N * log N)
- Auxiliary Space: O(N)
Related Topic: Segment Tree
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
