자료구조-펜윅트리 핵심 코드 | c++

잦은 업데이트와 합을 구하는데 사용되는 펜윅 트리입니다. 

코드가 암기만 하면 너무 간단하여 저는 인덱스트리보다 펜윅트리를 선택했습니다.

뭔가 인덱스트가 조금 더 범용적으로 사용된다긴 하지만 저는 제 기억력의 한계를 알고 있기 때문에 펜윅트리로 정착했습니다. 

---

업데이트 코드입니다.

int tree[100];

void update(int a, int diff)
{
    while(a < 100)
    {
        tree[a] += diff;
        a += (a &-a);
    }
}

---

합! 코드입니다.

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

---

확실히 인덱스 트리보다 훨씬 더 코드가 간결하고 간단합니다..... 이제 남은건 이걸 활용해서 문제를 푸는일뿐....

사실 왠만한 알고리즘 시험에서 단순하게 펜윅트리만 사용해서 해결되는 문제는 나오지 않습니다. 펜윅트리는 거들뿐.