Fenwick Tree (Binary Index Tree)

코드

#include <stdio.h>

typedef long long int lld;

int a[500002], num[1000002], n;
lld tre[500002];

lld sum(int idx) {
    lld ret = 0;
    while (idx > 0) {
        ret += tre[idx];
        idx -= (idx & -idx);
    }
    return ret;
}

void update(int idx, int diff) {
    while (idx <= n) {
        tre[idx] += diff;
        idx += (idx & -idx);
    }
}

int main()
{
    int i, t;
    lld ret = 0;

    scanf("%d", &n);
    for (i = n; i >= 1; i--) {
        scanf("%d", &t);
        num[t] = i;
    }

    for (i = 1; i <= n; i++) {
        scanf("%d", &t);
        a[i] = num[t];
    }

    for (i = 1; i <= n; i++) {
        ret += sum(a[i]);
        update(a[i], 1);
    }

    printf("%lld", ret);
}

문제에 대한 코드 : https://www.acmicpc.net/problem/7578 (공장)

정리

• i & -i 를 하면 i 를 비트로 나타냈을 때 마지막 1의 자리를 알 수 있다.
• sum(idx) : 1번부터 idx번까지의 합을 가져온다
• update(idx, diff) : idx번의 원소에 diff 개를 더한다

관련문제

• 세그먼트 트리 문제와 관련 있

참고자료

• 백준 (https://www.acmicpc.net/blog/view/21