**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, index, value}
- {2, L, R}

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

- For query of type 1: Update arr[index] = val.
- 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:

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