[2021/08/13][짤막한 이야기 - 구간합(응용)]

[2021/08/13][짤막한 이야기 - 구간합(응용)]
앞선 포스트에서 구간합에 대한 이야기를 했다.
구간합은 미리 합배열(SumA)을 생성하여 구간합 연산 속도를 O(N)에서 O(1)로 낮출 수 있다.
그러므로 기존에는 O(N*Q)(N은 데이터 개수, Q는 질문 개수)였던 시간복잡도가 O(Q) 수준으로 낮출 수 있었다.
그런데 만약 A 배열내의 숫자가 변경될 수 있다면 어떻게 될까?
Q에 단순히 구간합을 묻는 질문의 개수가 아니라 A 배열내의 특정 위치의 숫자를 다른 값으로 바꾸는 연산도 포함되어 있다면 이야기가 달라진다.
예를 들어 A[1]의 값을 5에서 7로 바꾼다면 SumA를 모두 업데이트해야 하기 때문이다.
A[1]을 업데이트하면 SumA는 1 ~ 9까지 모두 업데이트해야하기 때문에 최악의 경우 시간복잡도가 O(N*Q)로 증가할 수도 있다.
이를 해결하기 위해서는 A 배열내의 숫자가 변경되어도 최소한의 횟수로 SumA를 복원할 수 있어야 한다.
O(N)의 복잡도를 가지는 SumA 업데이트 과정을 더 빠르게 수행하려면 어떻게 해야할까?
그 해답은 앞서 포스팅한 바 있는 “이진 탐색”과도 관련이 있다.
[관련된 짤막한 이야기 - 구간합[2021/08/11]]
[관련된 짤막한 이야기 - 이진 탐색[2021/07/26]]
#이야기 #루니프 #알고리즘 #구간합 #이진탐색

[2021/08/13][Short Story - Prefix Sum(Application)]
In the previous post, I talked about the prefix sum.
The prefix sum can be reduced from O(N) to O(1) by generating the sum array (SumA) in advance.
Therefore, the time complexity, which used to be O(N*Q) (N is the number of data and Q is the number of queries), could be reduced to O(Q).
But what if the number in the A array can be changed?
The story is different if Q includes not just the number of queries asking for the sum of the intervals, but also the operation of replacing the number of positions in array A with a different value.
For example, if the value of A[1] is changed from 5 to 7, almost all SumA needs to be updated.
Updating A[1] may increase the worst-case time complexity to O(N*Q) because SumA needs to update all from 1 to 9.
To solve this problem, even if the number in array A changes, SumA must be restored with the least operation.
How can we perform the SumA update process faster?
The answer also relates to the "Binary Search" that was posted earlier.
[Related Short Story - Prefix Sum[2021/08/11]]
[Related Short Story - Binary Search[2021/07/26]]
#Story #LootNiP #Algorithm #PrefixSum #BinarySearch