[C++] 펜윅 트리(Fenwick Tree)

펜윅 트리(Fenwick Tree)

펜윅 트리는 바이너리 인덱스 트리(Binary Indexed Tree)라고도 부른다. 순서를 갖는 데이터가 주어졌을 때, 구간의 대표 값이나 연산 결과를 빠르게 얻을 수 있는 트리 형태의 자료구조이다.

 

기본 원리

https://www.acmicpc.net/blog/view/21

펜윅 트리 (바이너리 인덱스 트리)

 

펜윅 트리를 구현하기 위해선 어떤 수를 이진수로 나타냈을 때 마지막 1의 위치를 알아야 한다.

 

이진수

 

마지막 1이 나타내는 값을 L[i]라고 표현할 때, L[3] = 1, L[10] = 2, L[12] = 4이 된다. 이때, 짝수는 0의 갯수(num)로 정해진다. (L[i] = 2^num)

 

아래 그림은 각 i에 대해 L[i]를 나타낸 표이다.

 

L[i]

 

수 N개를 A[1] ~ A[N]이라고 했을 때, Tree[i]는 A[i]부터 앞으로 L[i]개의 합이 저장되어 있다.예를 들어, Tree[12]에는 A[12]부터 앞으로 L[12] = 4개의 합인 A[9] + A[10] + A[11] + A[12]가 저장되어 있다.

 

아래 그림은 각 i에 대해 Tree[i]를 나타낸 표이다.

 

Tree[i]

 

https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

#include <iostream>
#include <vector>
using namespace std;

long long sum(vector<long long>& tree, int index)
{
    // 합 구하기
    // index를 이진수로 나타낸 뒤 비트 내 1이 없어질 때까지 더한다.
    // index = 13일 때, A[1] + ... + A[13] = tree[1101] + tree[1100] + tree[1000]

    long long ans = 0;
    while (index > 0) {
        ans += tree[index];
        index -= (index & -index); // 최하위 비트(1) 지우기
    }
    return ans;
}

void update(vector<long long>& tree, int index, long long value)
{
    // 변경
    // sum과 반대로 최하위 비트에 1을 더한다.

    while (index < tree.size()) {
        tree[index] += value;
        index += (index & -index);
    }
}

int main()
{
    int n, m, k;
    cin >> n >> m >> k;

    vector<long long> arr(n + 1), tree(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        update(tree, i, arr[i]);
    }

    m += k;
    while (m--) {
        int num;
        cin >> num;

        if (num == 1) {
            int index;
            long long val;
            cin >> index >> val;

            long long diff = val - arr[index];
            arr[index] = val;

            update(tree, index, diff);
        }
        else if (num == 2) {
            int left, right;
            cin >> left >> right;
            cout << sum(tree, right) - sum(tree, left - 1) << '\n';
        }
    }
}

 

문제

 

https://www.acmicpc.net/problem/2934

2934번: LRH 식물

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

vector<ll> tree(200001);

int sum(int index)
{
	int ans = 0;
	while (index > 0) {
		ans += tree[index];
		index -= index & -index;
	}
	return ans;
}

void update(int index, int num)
{
	while (index <= tree.size()) {
		tree[index] += num;
		index += index & -index;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	while (n--) {
		int a, b;
		cin >> a >> b;

		int sumA = sum(a), sumB = sum(b);
		cout << sumA + sumB << '\n';

		// 기본 원리
		// [a, b] 구간에 1을 더하려면
		// a부터 1을 더한 후 (update(a, 1)) b+1부터 -1을 빼면 된다. (update(b+1, -1))

		// 꽃이 핀 곳에는 다시 피지 않으므로 0으로 만든다.		
		update(a, -sumA); // a만 -sumA가 적용된다.
		update(a + 1, sumA);
		update(b, -sumB); // b만 -sumB가 적용된다.
		update(b + 1, sumB);

		// 꽃이 필수있는 구간에 1을 넣는다.
		update(a + 1, 1); // a~b에 1을 더한다.
		update(b, -1);
	}
}

 

https://www.acmicpc.net/problem/5419

5419번: 북서풍

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

class Point {
public:
	int x, y;
	int index; // x좌표 크기 순위
};

int sum(vector<int>& tree, int index)
{
	int ans = 0;
	while (index > 0) {
		ans += tree[index];
		index -= (index & -index);
	}
	return ans;
}

void update(vector<int>& tree, int index, int value)
{
	while (index < tree.size()) {
		tree[index] += value;
		index += (index & -index);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;

		vector<Point> v;
		vector<int> tree(n + 1);
		for (int i = 0; i < n; i++) {
			Point data;
			cin >> data.x >> data.y;
			v.push_back(data);
			update(tree, i + 1, 1); // 펜윅트리 갱신
		}

		// 좌표 압축
		sort(v.begin(), v.end(), [](auto& a, auto& b) {
			if (a.x == b.x)
				return a.y > b.y;
			return a.x < b.x;
			});

		for (int i = 0; i < n; i++)
			v[i].index = i;

		sort(v.begin(), v.end(), [](auto& a, auto& b) {
			if (a.y == b.y)
				return a.x < b.x;
			return a.y > b.y;
			});

		// 펜윅트리 
		long long total = 0;
		for (int i = 0; i < v.size(); i++) {
			total += sum(tree, n) - sum(tree, v[i].index + 1);
			update(tree, v[i].index + 1, -1);
		}
		cout << total << "\n";
	}
}