길이 N짜리 배열이있는데


예를들어 배열의 인덱스 L 부터 R 까지 1씩 빼라는 업데이트 요청이 여러개있으면


요청마다 배열의 L원소부터 R까지 반복문 돌려서 1씩 빼는게 아니라 (요청마다 시간복잡도 = N)








이렇게 하라는데


내가 이해한게 맞는지 봐주심 ㄳㄳ


배열의 카피본을 만든다음


1. 요청마다 카피본의 L 에 1 더하고 빼고 R+1 에 1더한다음 (요청마다 시간복잡도 1)


2. 막판에 카피본의 구간합을 만들어서


3. 이 카피본 구간합과 오리지널 구간합과의 차이를 구한뒤 이 차이를 원래배열에 빼주면


되는거 맞음?


예시:


오리지널 배열 = [1, 2, 3, 4, 5]

오리지널구간합 = [1, 3, 6, 10, 15]

1씩 빼라는 업데이트 요청 = [0~2, 1~2]


위에서 말한 파란색 과정을 진행한뒤:

카피본 = [0, 1, 3, 6, 5]


카피본구간합 = [0, 1, 4, 10, 15]


오리지널 구간합과 카피본 구간합의 차이 = [1, 2, 2, 0, 0]


오리지널에다 이 차이를 갖다 빼서 결과물로 나온 최종 배열 = [0, 0, 1, 4, 5]




이거맞음? 맞는거 같긴한데



야 근데 이런거는 어떻게 아는거야? 키워드 뭐라 검색하면 나오냐;; 이런게 바로 웰노운이라는 것들임? 나 지금 이거 처음봐서 존나 기발함을 느끼고있는데..


종만북에 나온적 있는 내용인가? 일단 복습해야 알겠지만 비슷한거 있었던거 같기도 하고