307. Range Sum Query - Mutable

문제

https://leetcode.com/problems/range-sum-query-mutable/

피드백

• 팬윅 트리 (binary index tree) 로 일단 풀었다.
  • read : log(N), wirte : log(N)
  • T[N] = T[lsb[N1]] + T[lsb[N2]] ... 총 연산 수가 log(N) 이 됨.
• 세그먼트 트리도 솔루션에 있다. 개인적으로 아이디어가 더 직관적임
  • input 원소를 리프 노드로 둠, 그리고 위에 이진 B+트리를 만드는 것 처럼 부모 노드들을 생성
  • 각 노드들은 자식노드들의 인덱스 범위와, 그 원소들의 합을 속성으로 가짐
  • [left, right] 범위를 주면, 리프 노드부터 시작해서 [left,k], [k,right] 가 되는 부모노드 2개를 찾아 원소합을 더한다.
  • index의 원소가 값이 바뀌면 그 값은 위로 전파된다... 부모노드.sum = left.sum + right.sum 이기에 형제 노드의 인덱스도 잘 구해서 계속 update 해 나가면 됨.