# Find Maximum Range of Query using Segment Trees

Here, we are providing the solution along with the program of a question based on finding the maximum range of query using segment trees.
Submitted by Indrajeet Das, on November 03, 2018

The following question/problem is asked on http://www.spoj.com/problems/GSS1/

Problem:

A sequence is given: A, A, ..., A[N] .( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ). Query defined as follows:

Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }.

Given M queries, your program must output the results of the queries.

Input

• First line will have input N
• Second line will have N numbers of the sequence
• Third line will input M
• Fourth line will have those M queries of two numbers

Output

Your program must output the results of the M queries, one query per line.

Example:

```    Input:
3
-1 2 3
1
1 2

Output:
2
```

Solution:

In this question, we need to use segment trees. But what data to store in each node, such that it is easy to compute the data associated with a given node If we already know the data associated with its two child nodes.

We need to find maximum sum subarray in a given range.

Let’s say we have 'a' as a parent node and p and q as its child nodes. Now we need to build data for a from p and q such that node a can give the maximum sum subinterval for its range when queried.

So for this do we need?

Maximum sum subarray in 'a' can be equal to:

1. Max subarray in p
2. Max subarray in q
3. Elements including both p and q

So for each node we need to store:

1. Maximum prefix sum
2. Maximum suffix sum
3. Total Sumtr
4. Best Sum

Max Suffix sum can be calculated by:

a.suffix = Max(q.suffix,q.total+p.suffix)

Similarly Max prefix sum can be calculated by:

a.prefix = Max(p.prefix,p.total+q.prefix)

Total = p.total + q.total

Best Sum: Max(p.suffix+q.prefix,max(p.best,q.best)).

Program:

```#include<bits/stdc++.h>

using namespace std;
#define INT_BITS 32

int maxSubarrayXOR(int set[], int n)
{
// Initialize index of
// chosen elements
int index = 0;

// Traverse through all
// bits of integer
// starting from the most
// significant bit (MSB)
for (int i = INT_BITS-1; i >= 0; i--)
{
// Initialize index of
// maximum element and
// the maximum element
int maxInd = index;
int maxEle = INT_MIN;
for (int j = index; j < n; j++)
{
// If i'th bit of set[j]
// is set and set[j] is
// greater than max so far.
if ( (set[j] & (1 << i)) != 0
&& set[j] > maxEle )
maxEle = set[j], maxInd = j;
}

// If there was no
// element with i'th
// bit set, move to
// smaller i
if (maxEle == INT_MIN)
continue;

// Put maximum element
// with i'th bit set
// at index 'index'
swap(set[index], set[maxInd]);

// Update maxInd and
// increment index
maxInd = index;

// Do XOR of set[maxIndex]
// with all numbers having
// i'th bit as set.
for (int j=0; j<n; j++)
{
// XOR set[maxInd] those
// numbers which have the
// i'th bit set
if (j != maxInd &&
(set[j] & (1 << i)) != 0)
set[j] = set[j] ^ set[maxInd];
}

// Increment index of
// chosen elements
index++;
}

// Final result is
// XOR of all elements
int res = 0;
for (int i = 0; i < n; i++)
res ^= set[i];
return res;
}

struct uni{
long parent;
long size;
};

int main(){
long N,M;
cin>>N>>M;
uni U[N+1];
long size[N+1];
for(long i =0;i<N;i++){
U[i].parent = i;
U[i].size = 1;
}
size = N;

for(long i =0;i<M;i++){
long u1,u2;
cin>>u1>>u2;
size[U[u1].size]--;
size[U[u2].size]--;
U[u1].size = U[u1].size + U[u2].size;
U[u2].size = U[u1].size;
size[U[u1].size]++;
cout<<"before loop\n";
while(U[u2].parent!=u2){
u2 = U[u2].parent;
}
cout<<"After loop\n";
U[u1].parent = u2;
}

int xorInput[N];
int count = 0;
for(int i =0;i<N;i++){
if(size[i]>0){
xorInput[count] = i;
count++;
}
}

cout<<maxSubarrayXOR(xorInput,count);

return 0;
}
```

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates