배열의 특정 구간에 대한 sum을 반복적으로 계산해야할 때 사용 📍구분 값을 변경하지 않는 경우 (immutable) 값을 변경하는 경우 (mutable) 1차원 prefix sum binary indexed tree (Fenwick tree) segment tree sqrt-decomposition 2차원 summed-area table (integral image) binary indexed tree (Fenwick tree) segment tree sqrt-decomposition 📍예시 (sum) A : array S : sum (계산의 편의상 0부터 시작) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A 1 3 11 6 7 10 14 9 18 16 5 4 2 8 19 S ..