ラインツリー

セグメントツリーと呼ばれる構造について説明し、C ++での簡単な実装を示します。 この構造は、線形配列のセグメントで関数の値を検索する必要があり、連続する要素のグループの値をすばやく変更できる必要がある場合に非常に役立ちます。

セグメントのツリーでのタスクの典型的な例：

最初はいくつかのデータで満たされた線形配列があります。 次の2種類のクエリ：

第1タイプ-配列[a..b]のセグメントの最大要素の値を見つけます。

2番目のタイプ-配列のi番目の要素をxに置き換えます。

「セグメント[a..b]のすべての要素にxを追加する」というクエリは可能ですが、この記事では考慮しません。

セグメントのツリーを使用すると、最大数だけでなく、結合性プロパティを満たす関数も検索できます。



この制限は、一部のセグメントの値の計算が使用されるという事実によるものです。



たとえば、値ではなく要素のシリアル番号を検索することもできます。

関数には、結果に影響を与えない「ニュートラル」引数があることが望ましいです。 たとえば、合計の場合は数値0：（a + 0 = a）、最大の場合は無限大：max（a、-inf）= aです。

行きましょう。

上記の問題を解決する最も簡単な（そして最も遅い）方法は、線形配列を取得し、彼らが私たちから望むことを忠実に行うことです。

このような実装では、リクエストへの応答を見つけるのにかかる時間はO（n）です。 平均して、最大値を見つけるにはアレイの半分を通過する必要があります。 肯定的な側面はありますが、要素の値を変更するにはO（1）時間かかります。 小さなアルゴリズムを実行すると、このアルゴリズムは2倍高速化できます。各要素のペアについて、最大値を見つけて別の配列に書き込みます。 次に、セグメントの最大値を検索するときに、要素の各ペアについて、大きい方の値がすでにわかっているので、比較するだけで済みます。 要求されたセグメントの境界は必ずしも均一ではないため、境界要素を慎重に確認するためだけに残ります。

この図は、チェックする必要のある要素を強調しています。







検索が2倍速くなるように、これらの配列の上にもう1つ入力できることは明らかであり、最上部の配列が1つの要素で構成されるまで、というように続きます。 ご想像のとおり、一番上の配列の単一要素の値は最大要素の値です。







いくつかの説明：ツリーの上部の横にある数字は、実際の配列におけるこの上部の位置です。 このツリーストレージの実装では、頂点の祖先と子孫を検索するのが非常に便利です。頂点iの祖先は番号i / 2、番号i * 2とi * 2 + 1の子孫を持ちます。 図から、配列の長さは2のべき乗であることが必要であることがわかります。 そうでない場合は、アレイの最後にニュートラル要素を追加できます。 構造を格納するためのメモリ消費量は2n〜4nです（nは要素の数です）。

「上から」の検索アルゴリズム（「下にもあります」）は、理解と実装の両方で非常に単純です（再帰に慣れていない人にとっては、これはすべてを困惑させるかもしれません）。

アルゴリズムは次のとおりです。

調査はトップ1（最上位）から開始します。

1.現在の頂点に、間隔l..rの最大値を知らせます。

「交差するエリア[a..b]と[l..r]？」

可能なオプション：

a。 まったく交差しないでください。

計算結果に影響を与えないように、中立要素（-∞）を返します。

b。 領域[l..r]は完全に[a..b]の内側にあります。

現在の頂点で計算された値を返します。

と 重複領域の別のオプション。

現在の頂点の子に同じ質問をし、それらの間の最大値を計算します（明確でない場合はコードを参照）。



ご覧のとおり、アルゴリズムは短いですが、再帰的です。 時間の複雑さはO（logN）であり、O（N）よりもはるかに優れています。 たとえば、長さが10 ^ 9の要素の配列では、約32の比較が必要です。

この構造の数値の変更はさらに簡単です。指定されたものから1番目までのすべての頂点を通過する必要があり、現在の値が新しい値よりも小さい場合は置き換えます。 O（log N）時間もかかります。

アルゴリズムの実装。

配列内の要素の数は1024（数値0..1023）以下であると想定されています。

1. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


   
   
   
   
2. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


   
   
   
   
4. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


   
   
   
   
5. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


   
   
   
   
7. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


   
   
   
   
8. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


   
   
   
   
10. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
11. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
12. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
13. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
14. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
15. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
16. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
17. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
18. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
19. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
20. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
21. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
22. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
24. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
25. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
26. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
27. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
28. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
30. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
31. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
32. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
33. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
34. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
35. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
36. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
37. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
38. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
39. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
40. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
41. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
43. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
44. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
45. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
46. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
47. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
48. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
50. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
51. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
52. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
53. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
54. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
55. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
56. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
57. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
58. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
59. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
60. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
61. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
62. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
63. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
64. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
65. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
66. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
67. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    
68. #include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }


    
    
    
    

#include <cstdio> #include <algorithm> using namespace std ; #define INF 1000000000 // , . #define TREE_REAL_DATA 1024 // int tree_data [ TREE_REAL_DATA * 2 ] ; // . // : p - ( ). // l, p - , tree_data[p] . // , p, . // a, b - , . int __tree_find_max ( int p, int l, int r, int a, int b ) { if ( b < l || r < a ) return - INF ; if ( a <= l && r <= b ) return tree_data [ p ] ; int r1 = __tree_find_max ( p * 2 , l, ( l + r ) / 2 , a, b ) ; // int r2 = __tree_find_max ( p * 2 + 1 , ( l + r ) / 2 + 1 , r, a, b ) ; // return max ( r1, r2 ) ; // } // . int tree_find_max ( int a, int b ) { return __tree_find_max ( 1 , 0 , TREE_REAL_DATA - 1 , a, b ) ; } // № . void tree_update ( int p, int x ) { p + = TREE_REAL_DATA ; // p , // . tree_data [ p ] = x ; for ( p / = 2 ; p ; p / = 2 ) { if ( tree_data [ p * 2 ] > tree_data [ p * 2 + 1 ] ) tree_data [ p ] = tree_data [ p * 2 ] ; else tree_data [ p ] = tree_data [ p * 2 + 1 ] ; } } // - -INF void tree_init ( ) { for ( int i = 0 ; i < TREE_REAL_DATA * 2 ; i ++ ) tree_data [ i ] = - INF ; } int main ( ) { tree_init ( ) ; while ( 1 ) { char c ; scanf ( "%c" , & c ) ; if ( c == 'Q' ) return 0 ; // if ( c == 'F' ) { // a..b int a, b ; scanf ( "%d%d" , &a , & b ) ; printf ( "%d \n " , tree_find_max ( a, b ) ) ; } if ( c == 'U' ) { // p x. int p, x ; scanf ( "%d%d" , & p, & x ) ; tree_update ( p, x ) ; } } }









ここでは、一般的に、そして最初にセグメントのツリーについて知るために必要なすべてのもの。

変更については、ボトムアップ計算アルゴリズム（偶然にも再帰的ではありません）を理解できますが、魅力的ではありません。 もちろん、セグメントのすべての要素（O（log N）を超える）に合計をすばやく追加することは価値がありますが、最初にセグメントのツリーを扱う人にとってはあまりにも面倒です。