Home » Data Structure

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[1], A[2], ..., 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[1] = 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;
}