[서론] 크기가 1000인 배열이 있다. 이 배열의 각 원소는 1부터 10까지의 수이다. 이때 i번째 원소부터 j번째 원소까지의 합을 구하고 싶다. 어떤 방법이 좋을까? 가장 먼저 떠오르는 것은 누적합을 이용한 방법일 것이다. Sk를 Arr[0] ~ Arr[k] 까지의 모든 원소의 합이라 정의할 때, 누적합을 이용해, 구간 (i, j)의 구간합을 Sj - S(i - 1) 로 O(1)에 구할 수 있다. 이 때, Arr의 원소 중 일부가 변경된다면 어떻게 될까? 올바른 구간합을 구하기 위해서는, 누적합을 저장해 놓은 배열을 다시 갱신해야 할 것이다. 배열의 크기가 N이고, 배열값의 변경이 M회 일어날 때 Worst Case에 시간복잡도는 O(NM)이 된다. 이는 N, M의 크기가 어느 정도 커지면 시간 효율..
