[CPP] 펜윅 트리 (Fenwick Tree)

#include <iostream>

const int MAX_SIZE = 10;

void update(int* TREE, int idx, int value) {
    for (++idx; idx <= MAX_SIZE+1; idx += (idx & -idx))
        TREE[idx] += value;
}

int sum(int *TREE, int s) {
    int r = 0;
    for (++s; s > 0; s &= (s-1))
        r += TREE[s];
    return r;
}

int main(int argc, char **argv) {
    int TBL[MAX_SIZE] = {0};
    int TREE[MAX_SIZE+1] = {0, };

    for (auto i = 0; i < MAX_SIZE; i++) {
        TBL[i] = i+1;
        update(TREE, i, TBL[i]);
    }

    // GET SUM from 1 ~ N
    for (auto i = 0; i < MAX_SIZE; i++)
        std::cout << sum(TREE, i) << ", ";
    std::cout << std::endl;
    
    return 0;
}