Segment Tree (Bottom Up)

결합법칙이 성립하는 operator * 가 있을 때, 한 원소의 값을 업데이트 하거나 a[l] * a[l+1] * … * a[r-1] * a[r] 을 빠르게 구할 때 쓰는 자료구조이다.

• 공간 복잡도 : O(n)
• 시간 복잡도
  • 한 점 업데이트 : O(logn)
  • 구간값 쿼리 : O(logn)

구간 업데이트 & 한 점 쿼리

구현을 약간 응용하면 구간 업데이트 및 한 점 쿼리를 하는 경우에도 사용할 수 있다.