Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction-  
2.
Solution Approach
3.
Algorithm -
3.1.
C++ code: 
4.
Algorithm Complexity: 
5.
FAQs
6.
Key takeaways-
Last Updated: Mar 27, 2024

Queries to calculate sum with alternating signs of array elements in a given range

Author Riya
1 upvote
gp-icon
Competitive programming
Free guided path
16 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction-  

This blog will discuss the problem "Queries to calculate sum with alternating signs of array elements in a given range."

In this problem, we will be given an array containing 'N' integers and 'q' queries of any of the following two types (the first element of the query is indicating its type, i.e., '1' or '2'):

  1. {1, index, value}
  2. {2, L, R}

and we have to do the following operations depending on the type of the query:

  1. For query of type 1: Update arr[index] = val. 
  2. For query of type 2: Print the sum with alternating signs of array elements in a range [L, R]        

Let's understand the problem with an example:

Suppose N = 5 and given array of integers is:

arr = { 6, 1, 4, 0, 3 }

And q = 3 and given queries of the form {L, R} are:

queries[][] = { { 2, 0, 3 }, { 1, 1, 2 }, {2, 1, 4} }

There are three queries. We will evaluate these queries in the following way:

  1. The first query is: { 2, 0, 3 }

This query is of type 2, so we have to calculate and print the sum with alternating signs of array elements in a range [0, 3].

Answer to Query 1 = arr[0] - arr[1] + arr[2] - arr[3] = 6 - 1 + 4 - 0 = 9

2.The second query is: { 1, 1, 2 }

This query is of type 2, so we have to update arr[1] = 2

So, now arr = { 6, 2, 4, 0, 3 }

3. The third query is: {2, 1, 4} 

This query is of type 2, so we have to calculate and print the sum with alternating signs of array elements in a range [1, 4].

Answer to Query 3 = arr[1] - arr[2] + arr[3] - arr[4] = 2 - 4 + 0 - 3 = -5

Now that we understand the problem let's discuss the approach to solve it in the next section.

Also read, Euclid GCD Algorithm

Solution Approach

This section will discuss the approach to solve the problem "Queries to calculate sum with alternating signs of array elements in a given range."  

A simple approach is to update arr[index] = value for a query of type 1, and for the query of type 2, traverse the array from L to R, calculate the sum with alternating signs of array elements and print it. In this approach, the time complexity will be O(Q * N) where ‘Q’ and ‘N’ are a number of queries and the number of elements in the array respectively. We can optimize the time complexity using the approach described below.

An efficient approach to solve this problem is to use a segment tree. We know that a segment tree is an efficient data structure to evaluate range sum queries and update queries. But here, we don't have to simply calculate the sum, but we have to calculate the sum with alternating signs. So, while creating a segment tree from the given array, store the negative of the array element for odd indices of the array. For "update queries," also check the index, whether it is even or odd, and update accordingly. Now, for "sum queries," if we have to calculate the sum starting from an even index, then the answer will be simply the result of the range sum query on the segment tree. But if the starting index is odd, then the answer will be the negative of the result of the range sum query on the segment tree. 

You can also check What is Recursion here.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Algorithm -

Step 1. First, write the main function. Inside the main function, call the function "buildSegmentTree()" to construct a segment tree from the given array and then iterate through all the queries and call the function to update or find sum depending on the query type.

Step 2. Write a function "buildSegmentTree()," which will take input an array of integers and its size and construct a segment tree. Inside the function "buildSegmentTree()," calculate the height and maximum size of the segment tree and allocate memory for an array of size equal to the maximum size of the segment tree. Then call a recursive function to build the segment tree, which will get the middle element and build the left and right subtree of the segment tree recursively. While constructing the segment tree, take care of the index, whether it is odd or even. If it is even, then simply store the array element into the segment tree. Else store the negative of the array element into the segment tree.

Step 3. Write the function "update()" to update the element at a given index for the query of type 1. Inside the function, if you find the index to update in the segment tree, check whether the index is even or odd. If it is even, update it with the given value. Else update it with the negative of the given value. If the index is not found, call the function recursively for the left and right subtree.

Step 4. Write a function "rangeQuery()," which returns the sum of elements in a given range [L, R] from the segment tree. Call the function recursively to get the sum of left and right subtree and then return their sum.

C++ code: 

// C++ program to evaluate the queries to calculate sum with alternating signs of array elements in a given range
#include <bits/stdc++.h>
using namespace std;


// Recursive function to construct Segment Tree for the subarray [start..end]
int recurBuildSegmentTree(int* segmentTree, int arr[], int start, int end, int si)
{

	// If there is one element in the subarray
	if (start == end) 
	{
		if(start % 2 == 0) {
		segmentTree[si] = arr[start];
	}
	else {
    	segmentTree[si] = -arr[start];
	}
		return arr[start];
	}


	// Else get the middle element then recursively call the function to create the left and right subtree
	int middle = start + (end - start)/2;


	// For left subtree
	int left = recurBuildSegmentTree(segmentTree, arr, start, middle, si * 2 + 1);

	// For right subtree
	int right = recurBuildSegmentTree(segmentTree, arr, middle + 1, end, si * 2 + 2);

	segmentTree[si] = segmentTree[si * 2 + 1] + segmentTree[si * 2 + 2];


	return segmentTree[si];
}


// Function for constructing a Segment Tree from a given array of integers
int* buildSegmentTree(int arr[], int n)
{

	// Calculate the height of the segment tree
	int x = (int)(ceil(log2(n)));


	// Calculate the maximum size of Segment Tree
	int max_size = 2 * (int)pow(2, x) - 1;


	// Allocating memory
	int* segmentTree = new int[max_size];


	// Call a recursive function to fill the allocated memory recursively
	recurBuildSegmentTree(segmentTree, arr, 0, n - 1, 0);


	// Return the constructed Segment Tree
	return segmentTree;
}


// Function to update element of a Segment Tree
void update(int* segmentTree, int index, int start, int end, int pos, int val)
{

	// If current node is a leaf node
	if (start == end) {

		// If current index is even
		if (start % 2 == 0) {
		
		// Update segmentTree[index]
		segmentTree[index] = val;
	    }
		else {
		
		// Update segmentTree[index]
		segmentTree[index] = -val;
		}
		return;
	}


	// Divide the segment tree elements into left and right subtree
	int mid = start + (end - start) / 2;


	// If element lies in left subtree
	if (mid >= pos) {
		update(segmentTree, 2 * index + 1, start, mid, pos, val);
	}

	// Else If element lies in right subtree
	else {
		update(segmentTree, 2 * index + 2, mid + 1, end, pos, val);
	}


	// Update segmentTree[index]
	segmentTree[index] = segmentTree[2 * index + 1] + segmentTree[2 * index + 2];
}


// Function to find the sum of array elements in the range [L, R]
int sumQuery(int* segmentTree, int start, int end, int L, int R, int index)
{

	// If start and end doesn't lie in the range [L, R]
	if (L > end || R < start) {
	return 0;
	}


	// If start and end lies in the range [L, R]
	if (L <= start && R >= end) 
	{
        	// Return the elements at index 'index'
	return segmentTree[index];
	}

	int mid = start + (end - start) / 2;


	// Find the sum from the left subtree
	int left = sumQuery(segmentTree, start, mid, L, R, 2 * index + 1);


	// Find the sum from right subtree
	int right = sumQuery(segmentTree, mid + 1, end, L, R, 2 * index + 2);


	// Return sum of left subtree sum and right subtree sum
	return left + right;
}


// Main Function
int main()
{

	// Number of integers in the given array
	int N =5;

	// Given array
	int arr[] = { 6, 1, 4, 0, 3 };

	// Given number of Queries
	int q = 3;

	// Given Queries
	vector<vector<int> > queries =  { { 2, 0, 3 }, { 1, 1,  2 }, {2, 1, 4} };
    	
	// Construct a Segment Tree from the given array
	int* segmentTree = buildSegmentTree(arr, N);

	for (int i = 0; i < q; i++) 
	{

		// Type of Query
		int queryType = queries[i][0];

		// If query is of type 1
		if (queryType == 1) {
			update(segmentTree, 0, 0, N - 1, queries[i][1], queries[i][2]);
			cout<<"Query "<<i+1<<" : Updated element at index "<<queries[i][1]<<" with a value "<<queries[i][2]<<endl;
		}

		// Else if query is of type 2
		else {
			if (queries[i][1] % 2 == 0) {                
				cout <<"Query "<<i+1<<" : "<<sumQuery(segmentTree, 0, N - 1, queries[i][1], queries[i][2], 0)<<endl;
		    }
			else {
				cout <<"Query "<<i+1<<" : "<<-sumQuery(segmentTree, 0, N - 1, queries[i][1], queries[i][2], 0)<<endl;
			}
		}
	}
}

 

Output:
Query 1 : 9
Query 2 : Updated element at index 1 with a value 2
Query 3 : -5

 

Algorithm Complexity: 

Time Complexity: O(Q * log (N))

In the above program to evaluate the queries to calculate sum with alternating signs of array elements in a given range, there are two types of queries on segment trees - update query and range sum query, both takes O(log N) time. So, the time complexity is O(Q * log(N)), where 'Q' is the number of queries and 'N' is the number of elements in the given array.

Space Complexity: O(N) 

In the above program to evaluate the queries to calculate sum with alternating signs of array elements in a given range, an array is created which represents the segment tree and stores'  N' elements. So, the space complexity is O(N), where 'N' is the number of elements in the given array.

FAQs

  1. What is a segment tree?
    A segment tree is a data structure that evaluates range sum queries and update queries efficiently. It is basically a binary tree storing segments of an array.
     
  2. What is the time complexity of evaluating range sum queries and update queries in a segment tree?
    The time complexity for both range sum query and update query in a segment tree is O(log N).
     
  3. For this question, how using the segment tree has optimized the time complexity as compared to brute force solution?
    In brute force solution, we have to traverse the given subarray [L, R] in each query but using segment trees, we can efficiently calculate the prefix sum in logarithmic time complexity. So, we have created a segment tree and stored the elements at odd indices with a negative sign, and using the prefix sum, we have obtained the required sum.

Key takeaways-

This article discussed the problem Queries to calculate sum with alternating signs of array elements in a given range,” the solution approach to this problem,  its C++ implementation, and its time and space complexity.

 If you want to solve similar problems such as Sum Of Two Arrays, Intersection Of Two Arrays etc. you can visit Coding Ninjas Studio.

If you think that this blog helped you share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.

Previous article
Queries to find the min index in a range [L, R] having at least value ele with updates
Next article
Maximize sum of array by reducing array elements to contain no triplets (i, j, k) where a[i] < a[j] and a[i] < a[k] and j <i < k
Guided path
Free
gridgp-icon
Competitive programming
16 chapters
217+ Problems
gp-badge
Earn badges and level up
Live masterclass