木の配列は区間の和のいくつかのよくある模型を求めます

原文住所:http://www.cppblog.com/MatoNo1/archive/2011/03/19/142226.html
樹状配列は区間求和問題において大きな役割を果たし,その3つの複雑度はいずれも線分樹よりはるかに低い…区間求和に関する問題は主に以下の3つのモデル(以下,A[1..N]を長さNのシーケンスとし,初期値は全0とする)がある.
(1)「改点求段」型、すなわちシーケンスAに対して以下の操作がある.
【1】修正操作:A[x]の値にcを加える.
【2】加算操作:このときのA[l..r]の和を求める.
これは最も容易なモデルであり,補助配列は必要ない.ツリー配列ではxからlowbit(x)(すなわちx&(-x))を減らすことで[1.x]全体の和が得られ,xからlowbit(x)を加えることでxのすべての傾向が得られる.コード:

void ADD(int x, int c)

{

     for (int i=x; i<=n; i+=i&(-i)) a[i] += c;

}


int SUM(int x)

{

    int s = 0;

    for (int i=x; i>0; i-=i&(-i)) s += a[i];

    return s;

}

操作【1】:ADD(x,c);
操作【2】:SUM(r)-SUM(l-1).
(2)「改段求点」型、すなわちシーケンスAに対して以下の操作がある.
【1】修正操作:A[l..r]間の全ての要素値にcを加算する.
【2】加算操作:このときのA[x]の値を求める.このモデルでは、A[1.i]がこれまでにどれだけ加算されたか(あるいは、これまでのすべてのADD(i,c)動作におけるcの総和と言える)を表す補助配列Bを設定する必要がある.
これまでのADD(x,c)のすべての動作について、x>=iの場合のみ、この動作はA[i]の値に影響を及ぼし(A[i]にcを加える)、初期A[i]=0のため、A[i]=B[i..Nの和があることがわかる.一方、ADD(i,c)(A[1..i]全体にcを加える)、B[i]にcを加えるとよい--B配列を操作すればよい.このようにしてこのモデルを「改点求段」型に変換したが、SUM(x)はB[1..x]の和ではなくB[x..N]の和を求めるものであり、この場合ADDとSUMにおける増減順を合わせるだけでよい(モデル1ではADDプラスSUMマイナス、ここではADDマイナスSUMプラス).コード:

void ADD(int x, int c)

{

     for (int i=x; i>0; i-=i&(-i)) b[i] += c;

}


int SUM(int x)

{

    int s = 0;

    for (int i=x; i<=n; i+=i&(-i)) s += b[i];

    return s;

}

操作【1】:ADD(l-1,-c);ADD(r, c);操作【2】:SUM(x).
 
(3)「改段求段」型、すなわちシーケンスAに対して以下の操作がある:【1】修正操作:A[l..r]間のすべての要素値にcを加える;【2】加算操作:このときのA[l..r]の和を求める.これは最も複雑なモデルであり、2つの補助配列が必要である:B[i]はA[1..i]がこれまでにどれだけ加算されたか(モデル2と同様)、C[i]はA[1..i]がこれまでにどれだけ加算されたかの総和(または、C[i]=B[i]*i)を表す.ADD(x,c)については、B[x]にcを加え、C[x]にc*xを加えればよい(C[x]とB[x]の関係から得られる).一方、ADD(x,c)動作は、A[1.i]の和に影響を及ぼす.x=i)A[1.i]の和にi*cを加える.すなわち、A[1..i]の和=B[i..N]の和*i+C[1..i-1]の和である.これにより、BとCの2つの配列は「改点求段」となる(ただし、Bは接尾辞和を求め、Cは接頭辞和を求める).また,このモデルでは,x=0ではSUM_を実行できないという境界を越えた問題に特に注意する必要がある.B動作およびADD＿C操作!
コード:

void ADD_B(int x, int c)

{

     for (int i=x; i>0; i-=i&(-i)) B[i] += c;

}


void ADD_C(int x, int c)

{

     for (int i=x; i<=n; i+=i&(-i)) C[i] += x * c;

}


int SUM_B(int x)

{

    int s = 0;

    for (int i=x; i<=n; i+=i&(-i)) s += B[i];

    return s;

}

int SUM_C(int x)

{

    int s = 0;

    for (int i=x; i>0; i-=i&(-i)) s += C[i];

    return s;

}


inline int SUM(int x)

{

    if (x) return SUM_B(x) * x + SUM_C(x - 1); else return 0;

}

操作【1】:ADD＿B(r, c); ADD_C(r, c);if(l＞1)｛ADD＿B(l−1,−c);ADD＿C(l−1,−c);｝動作【2】:SUM(r)−SUM(l−1).