1) i번째 데이터를 b로 바꾸기
2) a~c의 데이터의 합 구하기
이 두 가지 단계를 반복한다고 하자.
단순 배열을 사용?
세그먼트 트리를 사용?
(1) 배열의 크기를 4*N으로 설정 (N:데이터의 개수)
(2) init() 함수가 (node,start,end)를 가지게 설정
(3) (1,0,N)부터 시작
(4) node가 leaf node일 때 (start=end+1)일 때, tree[node]를 설정하고 반환
(5) node가 leaf node가 아닐 때, (2x,start,mid), (2x+1,mid,end)의 함수값 2개를 더해 tree[node]에 저장 후 반환
class SegTree:
# (1)~(3) 설정
def __init__(self,N,A):
self.A=A
self.tree=[0]*4*N
self.init(1,0,N)
# (4),(5) 설정
def init(self,node,left,right):
if left+1==right:
self.tree[node]=self.A[left]
else:
mid=(left+right)//2
self.tree[node]=self.init(node*2,left,mid)+self.init(node*2+1,mid,right)
return self.tree[node]
[start,end)의 범위 합을 구할 때, 현재 노드가 (node,left,right)이면 다음과 같은 3가지 경우가 생김
- [left,right)가 [start,end)에 완전히 포함되는 경우
=> tree[node] 반환- [left,right)가 [start,end)에 부분만 포함되는 경우
=> [left,mid), [mid,right)의 범위로 다시 합을 구해 더하고, 그 값을 반환 함- [left,right)와 [start,end)가 교집합이 없는 경우
=> 고려해주지 않아도 된다 (0 return)
def sum(self,node,left,right,start,end):
if start<=left and right<=end:
return self.tree[node]
if right<=start or end<=left:
return 0
mid=(left+right)//2
return self.sum(node*2,left,mid,start,end)+self.sum(node*2+1,mid,right,start,end)
update시에 2가지 고려사항이 있음
- [left,ringt)안에 target번째가 속한 경우
=> tree[node]+=value 실행 후,
node가 leaf node가 아니라면 [left,mid), [mid,rignt)범위로 다시 함수 실행- 아닌 경우
=> 고려하지 않아도 됨
def update(self,node,left,right,target,value):
if left<=target<right:
self.tree[node]+=value
if left+1==right: return
# leaf node가 아닌경우, 해당 원소를 포함 한 다른 node 찾아서 update함
mid=(left+right)//2
self.update(node*2,left,mid,target,value)
self.update(node*2+1,mid,right,target,value)