pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

右方向の和を求めるBIT

本当にどうでもいい内容です。




以下のように書けば sum(a[0..k]) が求められます。1-indexedのBITを0-indexedとして使うために最初にk++しています。

const int N = 1e5;
int bit[N + 1];

void bitadd(int k, int v) {
	for (k++; k <= N; k += k & -k) {
		bit[k] += v;
	}
}

int bitsum(int k) {
	int sum = 0;
	for (k++; k > 0; k -= k & -k) {
		sum += bit[k];
	}
	return sum;
}

以下のように書けば sum(a[k..n-1]) が求められます。addとsumのfor部分が逆になっただけですね。

const int N = 1e5;
int bit[N + 1];

void bitadd(int k, int v) {
	for (k++; k > 0; k -= k & -k) {
		bit[k] += v;
	}
}

int bitsum(int k) {
	int sum = 0;
	for (k++; k <= N; k += k & -k) {
		sum += bit[k];
	}
	return sum;
}

考え方は普通のBITと同じです。BITの原理をよく理解してない方は、これを練習問題だと思って考えてみると良いと思います。

実際に以下のコードを走らせてみましょう。

#include <iostream>

using namespace std;

const int N = 1e5;
int bit[N + 1];

void bitadd(int k, int v) {
	for (k++; k > 0; k -= k & -k) {
		bit[k] += v;
	}
}

int bitsum(int k) {
	int sum = 0;
	for (k++; k <= N; k += k & -k) {
		sum += bit[k];
	}
	return sum;
}

int main() {
	for (int i = 0; i < 10; i++) {
		bitadd(i, i + 1);
	}
	for (int i = 0; i < 10; i++) {
		cout << bitsum(i) << " ";
	}
	cout << endl;
}

実行結果は以下のようになります。

55 54 52 49 45 40 34 27 19 10


こんなことしなくてもk=n+1-kと変換すればいいだけの話ですし、和なら左方向だけ分かれば十分です。minBITのときに役に立つかなぁと思って書きました。