Could someone give a "for dummies" version of explanation of code for the problem SEGMENTQ?

gonecase · March 31, 2017, 6:34pm

I came across this problem:

I understood the concept. But I am not able to understand the implementation, primarily because I am relatively new to Segment Trees. Can someone give clear, commented code that they wrote to solve the same problem and also explain the same?

shraeyas · March 31, 2017, 7:29pm

Here’s the video I watched to understand Segment Trees

Here’s my code

github.com

Shraeyas/SPOJ-Solutions/blob/master/Range minimum query.cpp

#include<iostream>
#define MAX 100000
#define MAX2 400000

using namespace std;

int *a = new int[MAX];
int *segtree = new int[MAX2];

void construct(long lo, long hi, long pos)
{
	if(lo == hi)
	{
		segtree[pos] = a[lo];
		return;
	}
	
	long mid = lo + (hi - lo)/2;
	
	construct(lo, mid, 2*pos+1);

This file has been truncated. show original

Tried to keep it simple.

And I guess the video is itself really very great. It will clear your doubts regarding the implementation part.