Given an array input[] of size ‘size’ with all the elements as 0s and a two-dimensional array Queries[][] containing queries of the following two types:
1 Left Right ele: Add ele to all the elements in the range [Left, Right].
2 ele: Print elements at the array's ele’th index.
Example 1
Input
Input[] = {0, 0, 0, 0, 0, 0, 0}
Size = 7
Query = { { 1, 0, 4, 100 },
{ 2, 2 },
{2, 5}};
Output
Element at 2 is 100
Element at 5 is 0
Explanation
Initially all the elements of the array are 0 but when the first query of type1 is executed all the elements in range 0 to 4 are updated with the value 100 hence after that when two queries of type 2 are executed so the element at index 2 is 100 and element at index is 5 is 0 because index 5 is not updated.
Approach
Range Update in a Segment Tree without using Lazy Propagation and Point Query to solve this problem. The main idea is to use the segment trees concept to do type 2 queries and the difference array to perform type 1 queries. Basically, a difference array is a technique that is used to range update in O(1) time. In a difference array, a new array is maintained.D[i] is the difference array of a given array. D[i] = input[i]-input[i-1] (for 0 to size) and D[0] = A[0] for 0 based indexing. The difference array may be used to run range update queries "left right ele" where left is the left index, right is the right index, and ele is the value to be added, and it can be used to return the original Array when all queries have been completed. Where updating range operations can be done in O(1) time.
Iterate on all the queries using a for loop and accordingly perform the operation after checking the type of query
If query is of type 1 then update segTree[Left] += ele and segTree[Right + 1] -= ele Using the concept of Range Update in a segment trees.
For query of type 2, we have to return the element at index ele for that find the sum of Array of elements in the range [0,ele] using the segment trees and print the value of sum obtained.
Code:
#include <bits/stdc++.h>
using namespace std;
// Function for Range Update in a Segment Tree array
void update(int segTree[], int idx, int start,int end, int pos, int ele)
{
// If current node is the leaf node
if (start == end) {
// Update segTree[idx]
segTree[idx] += ele;
}
else {
// Left and right subtree division
int mid = (start + end) / 2;
// Check if pos lies in left subtree
if (pos <= mid) {
// Search pos in left subtree
update(segTree, 2 * idx, start, mid, pos, ele);
}
else {
// Search pos in right subtree
update(segTree, 2 * idx + 1, mid + 1, end,pos, ele);
}
// Update Tree[idx]
segTree[idx] = segTree[2 * idx] + segTree[2 * idx + 1];
}
}
// Function for finding the sum of all elements in range [0,Right]
int sum(int segTree[], int idx, int start,int end, int qleft, int qright)
{
// Base case
if (qleft == start && qright == end)
return segTree[idx];
if (qleft > qright)
return 0;
// Left and right subtree division
int mid = (start + end) / 2;
// It return sum of elements in the range
return sum(segTree, 2 * idx, start, mid, qleft, min(mid, qright))
+ sum(segTree, 2 * idx + 1, mid + 1, end,max(qleft, mid + 1), qright);
}
// Function to find eleth element
void getElementAtindexele(int segTree[], int ele, int size)
{
// Print element at index ele
cout << "Element at " << ele << " is "<< sum(segTree, 1, 0, size - 1, 0, ele) << endl;
}
// Range Update in a Segment Tree from [left,right]
void update_in_range(int segTree[], int Left,int Right, int ele, int size)
{
// Update arr[l] += X
update(segTree, 1, 0, size - 1, Left, ele);
// Update arr[R + 1] += X
if (Right + 1 < size)
update(segTree, 1, 0, size - 1, Right + 1, -ele);
}
int main()
{
// array size
int size = 7;
// Segment tree
int segTree[4 * size + 5] = { 0 };
// array
int input[] = { 0, 0,0,0,0,0,0 };
// Queries array
vector<vector<int> >Query = { { 1, 0, 4, 100 },
{ 2, 2 },
{2,5}};
// Total queries
int totalQuery = Query.size();
// Iterating on all the queries to do Range Update in a Segment Tree
for (int i = 0; i < totalQuery; i++) {
// Operate on their respective types of queries
if (Query[i][0] == 1)
update_in_range(segTree, Query[i][1],Query[i][2], Query[i][3], size);
else
getElementAtindexele(segTree, Query[i][1], size);
}
}
Output:
Element at 2 is 100
Element at 5 is 0
Time Complexity
O(Q * log(N))
The time complexity to do Range Update in a Segment Tree without using Lazy Propagation and Point Query is O(Q * log(N)), where ‘N’ is the size of the Array. Since we are creating an extra array to store the elements in the form of a segment tree, iterating in the segment tree will only cost log(N) time, where ‘N’ represents a total number of nodes in the tree. So if we operate for Q queries ,given in the input, the average time complexity for every query can be estimated as O(Q * log(N)).
The space complexity to do Range Update in a Segment Tree without using Lazy Propagation and Point Query is O(N), where N is the size of the Array since we are creating an extra array to store the elements in the form of a segment tree.
FAQs
What are segment trees? A Segment Tree is a data structure that can successfully answer range queries over an array while also allowing the Array to be modified.
Where are segment trees used? When there are several range queries on an array and changes to the same Array's elements, a Segment Tree is employed. A segment tree can solve the problem in less time compared to the brute force approach.
Key Takeaways
In this blog, we discussed the solution to do Range Update in a Segment Tree without using Lazy Propagation and Point Query along with the solution, the article also focused on the time and space complexity of the solution.
If you want to learn more about segment trees and want to practice some quality questions which require you to excel your preparation a notch higher, then you can visit our Guided Path for segment trees on Coding Ninjas Studio.To be more confident in data structures and algorithms, try out our DS and Algo Course. Until then, All the best for your future endeavors, and Keep Coding.
39+ registered 