せでぃのブログ

ブログ初心者おいどんのどうでもいい愚痴やどうでもいい愚痴やどうでもいいマメ知識などを披露するチラシの裏です。

セグメント木の累積和が上手くいかんなぁ

20150114追記:解決したのでリンクを追加。
セグメント木の累積和できた - せでぃのブログ



社会人10年目から始める競技プログラミングのすすめ - kuuso1のブログ
 気になってたプログラムに取り組んでみた。
 計算回数の軽減を至上の目的とした累積和の課題で、セグメント木というものを使うらしい。確かにツリーのアップデートはよくできてるなぁと感心してしまった。番号の総数が2の累乗(2^n)になってるからいいけど、なってなかったらこれ相当嫌らしいよなぁw


問題及び入力例。
csny/segment-tree · GitHub
プログラム本体はここ。
segment-tree/main.m at master · csny/segment-tree · GitHub


 問題はここ。というか情けないことにセグメント木を使って累積を出すメインのところなんだけども。
 おいどんは、セグメント木を使って最初に全ての累積和を出して引き算するという形

こんな
(n[1]+n[2]+…+n[b])-(n[1]+n[2]+…+n[a-1])

を取ってみたんだが、ご覧の通り羅列してみたけどどうしても簡単なループで書き表すような規則性が見つからない。リンク先のように足し算だけの方がうまい書き方あるんかなぁ。いや、うーんんんんん……、思いつかん!!
 要素数160とかも想定しなきゃいけない訳で、何か、式にできるはずなんだけどね。

// [0]〜[14]はセグメント木用の小計、実際の数字は[15]〜[30]
int tree[31]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,8,14,9,19,17,19,18,8,4,5,9,15,11,20,7,2};
// 与えられた番号(1<=x<=16)の累積和
int sum[17];

// 与えられた番号a,b(1<= a < b <=16)間の累積和を返す
int sum_sequence(int a, int b){
    sum[16]=tree[0];
    sum[15]=tree[1]+tree[5]+tree[13]+tree[29];
    sum[14]=tree[1]+tree[5]+tree[13];
    sum[13]=tree[1]+tree[5]+tree[13]+tree[27];
    sum[12]=tree[1]+tree[5];
    sum[11]=tree[1]+tree[11]+tree[25];
    sum[10]=tree[1]+tree[11];
    sum[9]=tree[1]+tree[23];
    sum[8]=tree[1];
    sum[7]=tree[3]+tree[9]+tree[21];
    sum[6]=tree[3]+tree[9];
    sum[5]=tree[3]+tree[19];
    sum[4]=tree[3];
    sum[3]=tree[7]+tree[17];
    sum[2]=tree[7];
    sum[1]=tree[15];
    sum[0]=0;
    return sum[b]-sum[a-1];
}