struct segment_tree
{
struct NODE{
int st , EN, value; // start , end
void init( int L,int R) {
st = L, EN = R;
if ( L == R) value = a[ L] ;
}
} g[ 3 * N] ;
void fill_CN( NODE & CN, NODE & LN, NODE & RN) // fill_current_node
{
CN.value = LN.value + RN.value ;
}
void build( int CN,int L,int R)
{
g[ CN] .init ( L,R) ;
if ( L == R ) return ;
int mid = ( L+ R) >> 1 ;
int LN = CN << 1 ;
build( LN,L,mid) ;
build( LN| 1 ,mid+ 1 ,R) ;
fill_CN ( g[ CN] , g[ LN] , g[ LN| 1 ] ) ;
}
void update( int CN, int pos,int val)
{
if ( g[ CN] .st == g[ CN] .EN )
{
g[ CN] .value = val;
return ;
}
int mid = ( g[ CN] .st + g[ CN] .EN ) >> 1 ;
int LN = CN << 1 ;
if ( mid >= pos) update( LN, pos,val) ;
else update( LN| 1 ,pos,val) ;
fill_CN( g[ CN] , g[ LN] ,g[ LN| 1 ] ) ;
}
int query( int CN, int L,int R)
{
int x = g[ CN] .st ;
int y = g[ CN] .EN ;
if ( y < L || x > R) return 0 ;
if ( L <= x && R >= y ) return g[ CN] .value ;
int LN = CN<< 1 ;
int ans = query( LN,L,R) ;
ans + = query( LN| 1 ,L,R) ;
return ans;
}
} s_tree;
c3RydWN0IHNlZ21lbnRfdHJlZQp7CiAgICBzdHJ1Y3QgTk9ERXsKICAgICAgICBpbnQgc3QgLCBFTiwgdmFsdWU7Ly8gc3RhcnQgLCBlbmQKCiAgICAgICAgIHZvaWQgaW5pdChpbnQgTCxpbnQgUil7CiAgICAgICAgICAgc3QgPSBMLCBFTiA9IFI7IAogICAgICAgICAgIGlmKEwgPT0gUikgdmFsdWUgPSBhW0xdOwogICAgICAgICB9CiAgICB9Z1szKk5dOwoKICAgIHZvaWQgZmlsbF9DTihOT0RFICZDTiwgTk9ERSAmTE4sIE5PREUgJlJOKSAvLyBmaWxsX2N1cnJlbnRfbm9kZQogICAgewogICAgICAgIENOLnZhbHVlID0gTE4udmFsdWUgKyBSTi52YWx1ZTsKICAgIH0KCiAgICB2b2lkIGJ1aWxkKGludCBDTixpbnQgTCxpbnQgUikKICAgIHsKICAgICAgICBnW0NOXS5pbml0KEwsUik7CgogICAgICAgIGlmKEwgPT1SICkgcmV0dXJuOwogICAgICAgIGludCBtaWQgPSAoTCtSKT4+MTsKICAgICAgICBpbnQgTE4gPSBDTiA8PCAxOwoKICAgICAgICBidWlsZChMTixMLG1pZCk7CiAgICAgICAgYnVpbGQoTE58MSxtaWQrMSxSKTsKCiAgICAgICAgZmlsbF9DTiAoZ1tDTl0sIGdbTE5dICwgZ1tMTnwxXSk7CiAgICB9CgogICAgdm9pZCB1cGRhdGUoaW50IENOLCBpbnQgcG9zLGludCB2YWwpCiAgICB7CiAgICAgICAgaWYoZ1tDTl0uc3QgPT0gZ1tDTl0uRU4pCiAgICAgICAgewogICAgICAgICAgICBnW0NOXS52YWx1ZSA9IHZhbDsKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KCiAgICAgICAgaW50IG1pZCA9IChnW0NOXS5zdCArIGdbQ05dLkVOKT4+MTsKCiAgICAgICAgaW50IExOID0gQ04gPDwgMSA7CiAgICAgICAgaWYobWlkID49IHBvcykgdXBkYXRlKExOLCBwb3MsdmFsKTsKICAgICAgICBlbHNlIHVwZGF0ZShMTnwxLHBvcyx2YWwpOwoKICAgICAgICBmaWxsX0NOKGdbQ05dLCBnW0xOXSxnW0xOfDFdKTsKICAgIH0KCiAgICBpbnQgcXVlcnkoaW50IENOLCBpbnQgTCxpbnQgUikKICAgIHsKICAgICAgICBpbnQgeCA9IGdbQ05dLnN0OwogICAgICAgIGludCB5ID0gZ1tDTl0uRU47CiAgICAgICAgaWYoeSA8IEwgfHwgeCA+IFIpIHJldHVybiAwOwoKICAgICAgICBpZihMIDw9IHggJiYgUiA+PSB5ICkgcmV0dXJuIGdbQ05dLnZhbHVlOwoKICAgICAgICBpbnQgTE4gPSBDTjw8MTsKCiAgICAgICAgaW50IGFucyA9IHF1ZXJ5KExOLEwsUik7CiAgICAgICAgYW5zICs9IHF1ZXJ5KExOfDEsTCxSKTsKICAgICAgICByZXR1cm4gYW5zOwogICAgfQoKfSBzX3RyZWU7
compilation info
prog.cpp:10:10: error: ‘N’ was not declared in this scope
}g[3*N];
^
prog.cpp: In member function ‘void segment_tree::NODE::init(int, int)’:
prog.cpp:8:31: error: ‘a’ was not declared in this scope
if(L == R) value = a[L];
^
prog.cpp: In member function ‘void segment_tree::build(int, int, int)’:
prog.cpp:19:9: error: ‘g’ was not declared in this scope
g[CN].init(L,R);
^
prog.cpp: In member function ‘void segment_tree::update(int, int, int)’:
prog.cpp:33:12: error: ‘g’ was not declared in this scope
if(g[CN].st == g[CN].EN)
^
prog.cpp:39:20: error: ‘g’ was not declared in this scope
int mid = (g[CN].st + g[CN].EN)>>1;
^
prog.cpp: In member function ‘int segment_tree::query(int, int, int)’:
prog.cpp:50:17: error: ‘g’ was not declared in this scope
int x = g[CN].st;
^
stdout