차분 배열(구간 갱신) 계산기

원래 배열 대신 이웃과의 차이 d[i] = a[i] − a[i−1]을 담아 두는 배열입니다. 구간 [l, r]에 v를 더할 때 안쪽은 나란히 v씩 올라가 차이가 변하지 않으므로, d[l] += v와 d[r+1] −= v 두 칸만 고치면 됩니다. 마지막에 누적합을 한 번 돌리면 원래 배열이 돌아옵니다.

길이 n에 명령이 m개일 때 O(nm)이 O(n+m)이 됩니다. 곧이곧대로 하면 명령마다 구간 길이만큼 써야 하는데, 차분 배열은 명령마다 정확히 2번 쓰고 마지막에 누적합으로 n번 씁니다. 구간이 길고 명령이 많을수록 차이가 커집니다.

구간이 끝나지 않고 배열 끝까지 v가 계속 더해집니다. 이 자료구조에서 가장 흔한 버그이며, 구간이 어차피 배열 끝까지인 짧은 예제로 시험하면 결과가 같아 보여 그냥 지나가기 쉽습니다. 이 도구는 빼먹었을 때의 결과를 옆 열에 나란히 보여 줍니다.

오른쪽 끝이 배열의 마지막 칸인 명령의 −v가 떨어질 자리가 필요하기 때문입니다. 이 칸을 두면 r+1이 배열을 넘어가는 경우를 조건문 없이 똑같이 처리할 수 있고, 누적합을 돌릴 때는 그냥 쓰지 않으면 됩니다. 조건문으로 건너뛰려다 어긋나는 것보다 안전합니다.

모서리 네 칸을 건드립니다. 왼쪽 위에 +v, 오른쪽 바깥과 아래 바깥에 각각 −v, 두 번 뺀 오른쪽 아래 모서리에 다시 +v를 놓는 포함–배제입니다. 되살릴 때는 행 방향과 열 방향으로 누적합을 한 번씩 돌립니다. 마지막 +v를 빼먹으면 사각형의 오른쪽 아래 바깥이 −v만큼 잘못 깎입니다.

갱신과 질의가 섞이는지가 다릅니다. 차분 배열은 명령을 전부 받고 마지막에 한 번 읽는 경우에만 이깁니다. 읽을 때마다 누적합을 다시 돌려야 하기 때문입니다. 갱신 사이사이에 값을 물어보는 상황이라면 펜윅 트리나 세그먼트 트리를 써야 합니다.

「몇 시부터 몇 시까지 몇 명이 있었는가」처럼 구간이 겹쳐 쌓이는 문제에 그대로 쓰입니다. 회의실 동시 사용 인원, 도로 구간별 통행량 누적, 이미지에서 사각형 영역 여러 개를 한꺼번에 밝히기 같은 것이 모두 같은 계산입니다. 일본 경진대회 쪽에서는 이모스법(いもす法)이라고도 부릅니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.