Segment Tree

옛날에 min max Tree를 공부 할 때 배열 특정 구간 내에서의 최대값과 최소값을 미리 저장해두어 범위가 주어 질 때 O(logN)시간내에 해결 했었는데 이렇게 구간 내의 특정 값을 저장해두는 방식을 Segment Tree라고 하나 보다.

범위가 주어지면 위 배열을 이용해서 해결하면 된다. 만약 3~6사이의 범위에 대해 구하라고 하면

이렇게 풀면 된다.

사실 이건 생각하는 것은 책 한번 보면 어렵지 않은데 이걸 어떻게 구현 할 것인가가 문제이다. 예전에는 이차원 배열 사용하며 메모리 낭비도 심하고 코드도 지저분하게 풀었는데 코드포스에 깔끔한 구현이 있어 참조해본다

void build(int id = 1, int l=0, int r=n){ if(r-l<2){ s[id]=a[l]; return; } int mid = (l+r)/2; build(id*2, l, mid); build(id*2+1, mid, r); //first set the children and set its order s[id]= s[id*2] + s[id*2+1]; } void modify(int p, int x, int id=1, int l=0, int r=n){ s[id]+=x-a[p]; if(r-l < 2){ a[p]=x; return; } int mid=(l+r)/x; if(p<mid) modify(p, x, id*2, l, mid); else modify(p, x, id*2+1, mid, r); } //x, y is range where you want to find sum int sum(int x, int y, int id=1, int l=0, int r=n){ if(x>=r || l>=y) return 0; if(x<=l && r<=y) return s[id]; int mid=(l+r)/2; return sum(x, y, id*2, l, mid)+ sum(x, y, id*2+1, mid, r); }

펜윅트리와는 다르게 Segment 트리는 구간의 최대값과 최소값 또한 저장 할 수 있고 갱신도 용이하다. 앞으로 자주 사용해야겠다.