Last Updated: 22 Apr, 2021

Maximum Subarray Sum Queries - ll

Hard

Asked in company

Problem statement

You are given an array “Arr” of size ‘N’. You are given ‘Q’ queries. There are two types of queries and they are defined as follows:

1.  “index” “value” in this query, set the value of arr[index] to value.
2.  ‘L’ ‘R’ in this query, you must find i and j such that L is less than or equal to i, and j is less than or equal to R, and i is not equal to j, such that the sum of arr[i] and arr[j] is maximized. Then, print the sum of arr[i] and arr[j].

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘Q’ denoting the number of elements in the array and number of queries respectively.

The second line of each test case contains ‘N’ space-separated integers, denoting the elements in the array “Arr”.

The next ‘Q’ lines contain three space-separated integers.
If the first integer is 1, Denote type 1 query, next 2 space-separated integers denote “index” and “value”.
If the first integer is 2, Denote type 2 query, next 2 space-separated integers denote ‘L’ and ‘R’.

Output Format :

For each test case, return the list of integers, where the ith of them denotes the answer of the ith type 2 query.

Output for each test case will be printed in a new line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 100000
1 <= Q <= 100000    
1 <= Arr[i], value < 10^9
1 <= index, L < R <= N

Where ‘T’ denotes the number of test cases,
‘N’ denotes the number of elements in the array,
‘Q’ denotes the number of queries,
“value” and “index” denote index and value in the query of type 1,
‘L’ and ‘R’ denote the range limits in the query of type 2.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

For each query of type 1, we can simply set Arr[index] = value.

For each query of type 2, we can simply iterate between ‘L’ and ‘R’ and store first highest in “maximum1” and second highest in “maximum2”. If the value Arr[i] is greater or equal to “maximum1” then do “maximum2” = “maximum1” and “maximum1” = Arr[i].

Algorithm:

Create an array “answer” to store the result of a query of type 2.
Iterate over the queries
If type is equal to 1:
- Do Arr[index] = value
If type is equal to 2:
- Iterate on the range from L to R and maintain two highest values in maximum1 and maximum2.
- If Arr[i] is greater or equal to maximum1:
  - Set “maximum2” = “maximum1”
  - Set “maximum1” = Arr[i]
- Else if Arr[i] is greater than maximum2:
  - Set “maximum2” = Arr[i]
- Store the sum of “maximum1” and “maximum2” in the array “answer”.
- Return the array “answer”.

Solve now

02 Approach

A Segment Tree is a data structure that allows us to efficiently perform range queries and update queries. Here in this problem in the segment tree, at any node, we store the two highest values of all the leaf nodes present in the subtree rooted at that node at any ode. Similarly, for maximum segment trees.

The first step in this approach is to build the segment tree in which each node stores the two highest values of all the leaf nodes present in the subtree rooted at that node.

Once we have built a segment tree, for each query of type 1, we will perform an update query in the segment tree that will set “value” at the leaf node that represents Arr[index]. For each query of type 2, we will perform a range query in the range ‘L’ to ‘R’ that will give us the two highest values in that range. Store the result of each query of type 2 in the array “answer” and return the array “answer”.

Algorithm:

Build the minimum segment tree in which each node stores the two highest values of all the leaf nodes present in the subtree rooted at that node.
Create an array “answer” to store the result of a query of type 2.
Iterate over the queries.
If type is equal to 1:
- Do an update query on the segment tree.
If type is equal to 2:
- Do a range query on the segment tree that will return the two highest values in the range from ‘L’ to ‘R’ and store them in the variable “maximum1” and “maximum2”.
- Store the sum of “maximum1” and “maximum2” in the array “answer”.
Return the array “answer”.

Solve now