Quick links
Latest articles
Internship
Members
New...
Algorithms
Discrete Mathematics
Big data
Languages
C
C++
C++ STL
Java
Data Structure
C#.Net
Android
Kotlin
SQL
Web
PHP
Python
JavaScript
CSS
Ajax
Node.js
Web prog.
Programs
C
C++
DS
Java
C#
Python
Aptitude
C
C++
Java
DBMS
Interview
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

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;
}





Quick links:
C FAQ(s) C Advance programs C/C++ Tips & Tricks Puzzles JavaScript CSS Python Linux Commands PHP Android Articles More...

Featured post:
Introduction to Linux (Its modes, Safety, Most popular Applications)
Linux Best Distribution Software (Distros) of 2018

Was this page helpful? Please share with your friends...

Are you a blogger? Join our Blogging forum.

Comments and Discussions



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



© https://www.includehelp.com (2015-2018), Some rights reserved.