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

Riya
1 upvote
Competitive programming
Free guided path
16 chapters
99+ problems

## 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.

## 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.

## 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.

Guided path
Free
Competitive programming
16 chapters
217+ Problems