我一直在努力理解query()
函数中最后6行的逻辑。
这是spoj上问题GSS1的代码。
解决方案链接
#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( "%dn", query( 1, 0, N - 1, l, r ).msum );
}
return 0; }
需要什么&no=right和查询函数中的返回。
是否有人建议更好的实现/教程fr段树。
在实现数据结构时,我无法将这些递归可视化。有小费吗?
需要什么&否=正确,然后返回查询功能
在这种情况下,查询到的分段同时进入两个子段。
假设你有一个覆盖区间1..n的节点,它有两个子节点1。。n/2和n/2+1。。n.如果你想查询某个区间[a,b],使得a<n/2<b然后你需要从左分支和右分支获得结果并将其组合(换句话说,将查询拆分为[a,n/2]和[n/2+1,b]获得2个结果并将它们组合
为了提高效率,您可以证明,对于任何查询,都只能有一个像这样的分割,因为间隔现在都触及了边界(因此,当您总是遍历其中一个子对象时,另一个子对象要么被忽略,要么完全落在查询内,然后返回下一个递归步骤)。
该代码用于非常高效的实现(不存储指向子级的指针,节点范围是隐式的)。如果您正在尝试学习/调试,请寻找更明确地存储内容的东西,或者自己编写一个。至少要正确缩进代码,将变量名更改为可读性更强的名称,并用middle
替换(a+b)/2
。这应该会使代码更容易理解。还要在纸上画出结构(总是有帮助的)。