Querying in segment tree

Question

I have been struggling to understand the logic of last 6 lines in query() function.

This is the code for the problem GSS1 on spoj.

Solution link

#include <cstdio>
#include <algorithm>
#define MAX 70000

using namespace std;

struct no {
int lsum, rsum, msum;
};

int array[ MAX + 1 ], sums[ MAX + 1 ];
no tree[ 4 * MAX + 1 ];

 void init( int node, int i, int j ) {
if ( i == j ) {
    tree[ node ] = ( ( no ) { array[ i ], array[ i ], array[ i ] } );
}
else {
    init( node * 2, i, ( i + j ) / 2 );
    init( node * 2 + 1, ( i + j ) / 2 + 1, j );
    no left = tree[ node * 2 ], right = tree[ node * 2 + 1 ];
    tree[ node ].lsum = max( left.lsum, sums[ ( i + j ) / 2 ] - sums[ i - 1 ] + right.lsum );
    tree[ node ].rsum = max( right.rsum, sums[ j ] - sums[ ( i + j ) / 2 ] + left.rsum );
    tree[ node ].msum = max( left.msum, max( right.msum, left.rsum + right.lsum ) );
}}

 no query( int node, int a, int b, int i, int j ) {
if ( a == i && b == j ) {
    return tree[ node ];
}
else if ( j <= ( a + b ) / 2 ) {
    return query( node * 2, a, ( a + b ) / 2, i, j );
}
if ( i > ( a + b ) / 2 ) {
    return query( node * 2 + 1, ( a + b ) / 2 + 1, b, i, j );
}
no left = query( node * 2, a, ( a + b ) / 2, i, ( a + b ) / 2 );
no right = query( node * 2 + 1, ( a + b ) / 2 + 1, b, ( a + b ) / 2 + 1, j );
return ( ( no ) {
            max( left.lsum, sums[ ( a + b ) / 2 ] - sums[ i - 1 ] + right.lsum ),
            max( right.rsum, sums[ b ] - sums[ ( a + b ) / 2 ] + left.rsum ),
            max( left.msum, max( right.msum, left.rsum + right.lsum ) )
            } ); }

int main() {
int i, N, q, l, r;
scanf( "%d", &N );
for ( i = 0; i < N; ++i ) {
    scanf( "%d", array + i );
    if ( i == 0 ) {
        sums[ i ] = array[ i ];
    }
    else {
        sums[ i ] = sums[ i - 1 ] + array[ i ];
    }
}
init( 1, 0, N - 1 );
scanf( "%d", &q );
for ( i = 0; i < q; ++i ) {
    scanf( "%d%d", &l, &r );
    --l;
    --r;
    printf( "%d\n", query( 1, 0, N - 1, l, r ).msum );
}
return 0; }

What is the need of that no = left && no = right and that return in query function.

Shall anyone suggest better implementation/tutorial fr segment tree.

I'm unable to visualize these recursions while implementing data structures. Any tip?

Answer 1

What is the need of that no = left && no = right and that return in query function

That's the case where the segment that you query to goes into both children.

Say you have a node that covers interval 1..n and has 2 children 1 .. n/2 and n/2+1 ..n. If you want to query some interval [a,b] such that a <=n/2 < b then you need to get the results from the left branch and the right branch and combine them (in other words split the query into [a, n/2] and [n/2 +1, b] get the 2 results and combine them.

For efficiency you can prove that there can be only one split like that for any query since the intervals are now touching the margin (so while you always traverse down one of the children, the other is either ignored or falls fully inside the query and you return on the next recursion step).

That code is for a very efficient implementation (you don't store pointers to the children, the node ranges are implicit). If you are trying to learn/debug look for something that stores things more explicitly, or write one yourself. At the very least indent the code properly, change variable names to something more readable and replace (a+b)/2 by middle. That should make the code easier to understand. Also draw the structure on paper (always helps).