펜윅 트리

구간 합을 세그트리보다 좀 더 간결하고 메모리를 아끼면서 구하는 구조.

 

다음 코드는 1base.

 

<코드>

struct fwt {
	vector<int> a;
	fwt(int n):a(n+1){}
	int sum(int p) {
		int ret = 0;
		while (p > 0) {
			ret += a[p];
			p -= (p & -p); //최종 비트 지우기
		}
		return ret;
	}
	void add(int p, int x) {
		while (p < a.size()) {
			a[p] += x;
			p += (p & -p); //최종 비트 더하기
		}
	}
};

int main() {
	FAST;
	fwt ft(10);
	for (int i = 1; i <= 10; i++)
		ft.add(i, i);
    //[0~i]합
	for (int i = 1; i <= 10; i++)
		cout << ft.sum(i) << " ";
	cout << '\n';

}