요약

배열의 누적 합은 대각선과 그 아래가 모두 1인 삼각 모양 행렬을 곱한 결과이고, 차분은 그 행렬의 역행렬을 곱한 결과다. 이렇게 보면 2차원 차분의 네 모서리 부호, 가로·세로 누적 순서를 바꿔도 되는 이유, 누적이 한 번 훑기로 끝나는 이유가 행렬의 기본 규칙 몇 개로 풀린다. 다만 이 그림은 빼기가 되는 계산(정수 덧셈, XOR 등)에서만 끝까지 맞는다. 최솟값·최댓값에는 되돌리는 행렬이 없고, 값이 자주 바뀌는 상황에서는 빠른 방법을 주지 않는다.

먼저 비교해 보기

표를 펼치기 전에 두 사례의 공통 구조와 대응 관계를 먼저 적어 본다. 왼쪽은 누적 합과 차분 배열의 계산이다1.

칸 번호는 코드처럼 0부터 센다. \(\mathbf{a} = (a[0], \dots, a[n-1])\)이고, P[0]을 뗀 누적 합을 \(\mathbf{p} = (P[1], \dots, P[n])\)로 쓴다. 곧 \(p_i = P[i + 1]\)이다. \(L\)은 대각선과 그 아래가 모두 1인 \(n \times n\) 행렬이고, 크기를 밝혀야 할 때는 \(L_k\)(\(k \times k\))로 쓴다. \(\mathbf{e}_i\)는 \(i\)번 칸만 1인 벡터다. 열벡터 \(\mathbf{u}\)와 행벡터 \(\mathbf{w}^\top\)(\(^\top\)는 행과 열을 바꾸는 전치)의 곱 \(\mathbf{u}\mathbf{w}^\top\)(바깥곱, outer product)는 \((i, j)\) 칸이 \(u_iw_j\)인 행렬이다.

알고리즘: 누적 합과 차분 배열 선형대수학: 아래삼각행렬과 역행렬
a = [3, 1, 4]를 앞에서부터 더해 P = [0, 3, 4, 8] \(\begin{pmatrix}1 & 0 & 0\\ 1 & 1 & 0\\ 1 & 1 & 1\end{pmatrix}\begin{pmatrix}3\\ 1\\ 4\end{pmatrix} = \begin{pmatrix}3\\ 4\\ 8\end{pmatrix}\)
a[i] = P[i + 1] − P[i]로 [3, 1, 4]를 되찾는다 \(\begin{pmatrix}1 & 0 & 0\\ -1 & 1 & 0\\ 0 & -1 & 1\end{pmatrix}\begin{pmatrix}3\\ 4\\ 8\end{pmatrix} = \begin{pmatrix}3\\ 1\\ 4\end{pmatrix}\)
길이 3인 0 배열의 1 ~ 2번에 2 더하기: D = [0, 2, 0, −2]에서 D[:3]을 누적하면 [0, 2, 2] \(L_4 \cdot 2(\mathbf{e}_1 - \mathbf{e}_3) = (0, 2, 2, 0)\)
3 × 3 격자의 (0, 0) ~ (1, 1)에 1 더하기: 표시 행이 (1, 0, −1), (0, 0, 0), (−1, 0, 1) \(\mathbf{u}\mathbf{u}^\top\), \(\mathbf{u} = (1, 0, -1)\)
가로로 누적한 뒤 세로로 누적하면 (1, 1, 0), (1, 1, 0), (0, 0, 0) 오른쪽에 \(L^\top\), 왼쪽에 \(L\)을 곱하면 \((L\mathbf{u})(L\mathbf{u})^\top\), \(L\mathbf{u} = (1, 1, 0)\)
대응 관계
알고리즘 수학 공통 구조
누적 P[i + 1] = P[i] + a[i] \(\mathbf{p} = L\mathbf{a}\) 앞쪽을 모두 더하기
차분 a[i] = P[i + 1] − P[i] \(\mathbf{a} = L^{-1}\mathbf{p}\), \(L^{-1}\)은 대각선 1, 바로 아래 −1 서로 되돌리는 계산(\(LL^{-1} = L^{-1}L = I\))
구간 합 P[r + 1] − P[l] P[0]까지 붙인 P에 행벡터 \((\mathbf{e}_{r+1} - \mathbf{e}_l)^\top\)를 곱하기 구간 = 두 끝의 차
구간 더하기 D[l] += x, D[r + 1] −= x \(L_{n+1}\)이 \(x(\mathbf{e}_l - \mathbf{e}_{r+1})\)를 l ~ r번만 x인 벡터로 보낸다. 마지막 칸은 늘 0이라 버린다(D[:n]) 두 끝 표시 → 구간
표시를 모두 적고 마지막에 한 번 누적 선형성 \(L(\mathbf{d}_1 + \mathbf{d}_2) = L\mathbf{d}_1 + L\mathbf{d}_2\) 겹쳐 더하기
2차원 네 모서리 표시 바깥곱 \(x\,\mathbf{u}\mathbf{w}^\top\), \(\mathbf{u} = \mathbf{e}_{r_1} - \mathbf{e}_{r_2+1}\), \(\mathbf{w} = \mathbf{e}_{c_1} - \mathbf{e}_{c_2+1}\) 행과 열이 따로 노는 표시
세로 누적, 가로 누적 왼쪽에 \(L_{\text{행}}\), 오른쪽에 \(L_{\text{열}}^\top\) 곱하기 양쪽에서 곱하기
한 칸 바꾸기 a[i] += x \(\mathbf{p}\)가 \(xL\mathbf{e}_i\)만큼 바뀐다 그 칸부터 끝까지 바뀐다

\(L_{\text{행}}\)과 \(L_{\text{열}}\)은 2차원 표시판의 행 수, 열 수 크기의 \(L\)이다. \(L^{-1}\)을 차분 행렬(difference matrix), \(L\)을 합 행렬(sum matrix)이라고도 부른다2. 미적분 쪽의 같은 짝(차분 ↔ 미분, 누적 ↔ 적분)은 합 ↔ 적분에 있다.

어디까지 같은가

  • P[0] = 0을 붙이면 정사각이 아니다. 코드처럼 P를 길이 n + 1로 쓰면, a에서 P로 가는 행렬 \(M\)은 \(L\) 위에 0으로 된 행 하나를 얹은 \((n + 1) \times n\) 행렬이다. 차분 a[i] = P[i + 1] − P[i]는 \(n \times (n + 1)\) 행렬 \(B\)를 곱하는 일이다. \(BM = I\)지만 \(MB \ne I\)다. 아무 수열에 \(B\)를 곱했다가 \(M\)을 곱하면 모든 칸에서 첫 값이 빠진다. 차분하면 시작값이 사라지고, 다시 누적하면 0부터 쌓기 때문이다. 미적분의 기본정리에서 미분하면 상수가 사라져 부정적분에 \(+C\)가 붙는 것과 같은 모양이다. 그래서 역행렬 이야기는 P[0]을 뗀 \(\mathbf{p}\)에서만 한다. P[0] = 0은 l = 0일 때의 예외를 없애려고 앞에 붙인 0 한 칸이다3.
  • 빼기가 되는 계산에서만 끝까지 맞는다. 정수·유리수의 덧셈, 나머지 덧셈(mod m), XOR(⊕)에서는 그대로 맞는다. XOR은 빼기도 XOR이다. \(x \oplus x = 0\)이라 같은 값을 한 번 더 XOR하면 지워진다. 비트마다 보면 2로 나눈 나머지의 덧셈이다. 그래서 \(L^{-1}\)의 −1이 1로 바뀌어, 대각선과 바로 아래 칸이 1인 모양이 된다. XOR로 누적한 P에서 구간 XOR은 P[r + 1] ⊕ P[l]이다. 최솟값·최댓값도 앞에서부터 모아 갈 수는 있다(누적 최솟값). 하지만 빼기가 없어 \(L^{-1}\)에 해당하는 계산이 없다. 그래서 누적 최솟값 두 개로는 구간 최솟값을 구할 수 없다. 이때는 세그먼트 트리를 쓴다4.
  • 부동소수점 수(float)로 계산하면 되돌리기가 어긋난다. 앞쪽 합이 크면 작은 값이 반올림에 묻힌다. a = [\(10^{16}\), 1, 1]을 float로 누적하면 P[2]와 P[3]이 모두 \(10^{16}\)이 된다. 그래서 P[3] − P[1] = 0인데, 실제 a[1] + a[2]는 2다. 차분해도 a[1]과 a[2]가 0으로 나온다. 식으로는 \(L^{-1}L = I\)여도, 반올림이 낀 계산은 원래 값으로 돌아오지 않는다.
  • 값이 자주 바뀌면 대응은 맞아도 쓸모가 끝난다. a[i]에 x를 더하면 \(\mathbf{p}\)는 \(xL\mathbf{e}_i\)만큼 바뀐다. \(L\mathbf{e}_i\)는 \(L\)의 \(i\)번 열이라 \(i\)번부터 끝까지 모두 1이다. 그래서 P[i + 1] ~ P[n]의 n − i칸을 모두 고쳐야 한다. 행렬 그림은 왜 느린지 보여 주지만, 빠른 방법은 주지 않는다. 값 바꾸기와 질문이 섞이면 세그먼트 트리가 필요한 까닭이다4.

이 연결로 얻는 것

수학에서 알고리즘으로.

  • 2차원 차분의 부호는 곱의 부호다. 표시판 \(x\,\mathbf{u}\mathbf{w}^\top\)의 \((i, j)\) 칸은 \(x\,u_iw_j\)다. \(\mathbf{u}\)는 \(r_1\)행에서 +1, \(r_2 + 1\)행에서 −1이고, \(\mathbf{w}\)는 \(c_1\)열에서 +1, \(c_2 + 1\)열에서 −1이다. 그래서 (r1, c1), (r1, c2 + 1), (r2 + 1, c1), (r2 + 1, c2 + 1)의 네 모서리는 \((+1)(+1)\), \((+1)(-1)\), \((-1)(+1)\), \((-1)(-1)\)로 +, −, −, +가 된다. 파괴되지 않은 건물에서 ‘줄마다의 표시를 다시 세로로 차분한다’는 것은 행 구간만 1인 벡터에 \(L^{-1}\)을 곱해 \(\mathbf{u}\)를 얻는 일이다5.
  • 누적 순서를 바꿔도 된다. 표시판 \(D\)를 세로로 누적하는 것은 왼쪽에 \(L_{\text{행}}\)을, 가로로 누적하는 것은 오른쪽에 \(L_{\text{열}}^\top\)을 곱하는 일이다. 행렬 곱셈의 결합법칙으로 \((L_{\text{행}}D)L_{\text{열}}^\top = L_{\text{행}}(DL_{\text{열}}^\top)\)이라 어느 쪽을 먼저 해도 같다6. 표시판 \(x\,\mathbf{u}\mathbf{w}^\top\)에 양쪽을 곱하면 \(x\,(L_{\text{행}}\mathbf{u})(L_{\text{열}}\mathbf{w})^\top\)가 된다. \(L_{\text{행}}\mathbf{u}\)는 \(r_1\) ~ \(r_2\)행만 1이고 \(L_{\text{열}}\mathbf{w}\)는 \(c_1\) ~ \(c_2\)열만 1이다. 그래서 결과는 직사각형 안만 x인 표다.
  • 직사각형 합 질문도 같은 꼴이다. 2차원 누적 합의 네 항 공식 S[r2 + 1][c2 + 1] − S[r1][c2 + 1] − S[r2 + 1][c1] + S[r1][c1]은 \((\mathbf{e}_{r_2+1} - \mathbf{e}_{r_1})^\top S\,(\mathbf{e}_{c_2+1} - \mathbf{e}_{c_1})\)다. 1차원 구간 합의 ‘두 끝의 차’를 행과 열에 한 번씩 쓴 것이다.

알고리즘에서 수학으로.

  • 빽빽한 행렬은 듬성한 역행렬로 풀면 빠르다. \(L\)은 0이 아닌 칸이 \(n(n+1)/2\)개라, 그 칸을 하나씩 곱해 더하면 곱셈만 그만큼이다. \(L^{-1}\)은 0이 아닌 칸이 \(2n - 1\)개뿐이다. 그래서 \(\mathbf{p} = L\mathbf{a}\)를 ‘\(L^{-1}\mathbf{p} = \mathbf{a}\)를 위에서부터 푸는 일(전진 대입)’로 보면, 한 줄에 덧셈 한 번으로 끝난다. 코드의 P[i + 1] = P[i] + a[i]가 바로 이 풀이다. 역행렬의 ‘역행렬을 구해 곱하지 말고 푼다’가 여기서는 ‘빽빽한 \(L\)을 만들지 말고 듬성한 \(L^{-1}\)로 푼다’가 된다.
  • 차분은 전진 대입이 한 줄로 줄어든 것이다. 거꾸로 \(L\mathbf{a} = \mathbf{p}\)를 LU 분해의 전진 대입으로 풀면, \(i\)번째 줄은 \(a_i = p_i - (a_0 + \cdots + a_{i-1})\)이다. 괄호 안은 이미 \(p_{i-1}\)이다. 그래서 \(a_i = p_i - p_{i-1}\), 앞 칸 빼기 한 번이다. 일반 아래삼각행렬의 전진 대입은 줄마다 앞 칸을 모두 써서 곱셈과 뺄셈이 합쳐 \(n(n-1)\)번, 약 \(n^2\)번이다(LU 분해에서 말한 풀이 한 번 약 \(2n^2\) 가운데 전진 쪽 절반)6. \(L\)의 모양 덕분에 이것이 뺄셈 \(n - 1\)번으로 줄어든다7.

전이 문제

두 확률변수 X, Y가 각각 1, 2, 3의 값을 갖는다. 결합 누적분포 \(F(i, j) = \Pr[X \le i, Y \le j]\)(\(\Pr[\cdot]\)은 확률)가 아래 표와 같다. 한 변수의 누적분포를 다룬 확률변수와 분포의 2차원 판이다8.

  j = 1 j = 2 j = 3
i = 1 0.10 0.15 0.20
i = 2 0.20 0.45 0.60
i = 3 0.25 0.65 1.00

(1) \(F\)를 \(3 \times 3\) 행렬로 본다. 결합 확률 \(Q_{ij} = \Pr[X = i, Y = j]\)를 되찾으려면 \(F\)의 왼쪽과 오른쪽에 각각 어떤 행렬을 곱해야 하는지 쓰고, 그 계산으로 \(Q\)를 구하라. (2) \(\Pr[2 \le X \le 3,\ 2 \le Y \le 3]\)을 \(F\)의 네 값으로 구하라.

답

(1) \(F\)는 \(Q\)를 세로로 한 번, 가로로 한 번 누적한 표라 \(F = LQL^\top\)이다. 그래서 왼쪽에 \(L^{-1}\)을, 오른쪽에 \((L^\top)^{-1} = (L^{-1})^\top\)를 곱한다. 왼쪽에서 \(L^{-1}\)을 곱하면 행마다 바로 위 행을 뺀다(세로 차분). 행이 (0.10, 0.15, 0.20), (0.10, 0.30, 0.40), (0.05, 0.20, 0.40)이 되고, 각각 \(\Pr[X = i, Y \le j]\)다. 여기에 오른쪽에서 \((L^{-1})^\top\)를 곱하면 칸마다 바로 왼쪽 칸을 뺀다(가로 차분). 결과는 아래 표이고, 합이 1이다.

  j = 1 j = 2 j = 3
i = 1 0.10 0.05 0.05
i = 2 0.10 0.20 0.10
i = 3 0.05 0.15 0.20

결합 누적분포는 결합 확률의 2차원 누적 합이고, 결합 확률은 그 2차원 차분이다. 흔한 실수는 오른쪽에도 \(L^{-1}\)을 곱하는 것이다. 그러면 칸마다 바로 오른쪽 칸을 빼서 답이 틀린다.

(2) \(F(3, 3) - F(1, 3) - F(3, 1) + F(1, 1) = 1.00 - 0.20 - 0.25 + 0.10 = 0.65\)다. 행렬로 쓰면 \((\mathbf{e}_3 - \mathbf{e}_1)^\top F\,(\mathbf{e}_3 - \mathbf{e}_1)\)이다(여기서는 번호를 1부터 센다). \(Q\)에서 오른쪽 아래 네 칸을 더해도 0.20 + 0.10 + 0.15 + 0.20 = 0.65다.

확인 문제

C1 a = [2, 7, 1]의 누적 합을 행렬 곱 \(L\mathbf{a}\)로 쓰고, \(L^{-1}\)을 적어 그것을 곱하면 차분이 됨을 보여라.

답: \(L = \begin{pmatrix}1 & 0 & 0\\ 1 & 1 & 0\\ 1 & 1 & 1\end{pmatrix}\)이고 \(L\mathbf{a} = (2, 9, 10)\)이다. \(L^{-1} = \begin{pmatrix}1 & 0 & 0\\ -1 & 1 & 0\\ 0 & -1 & 1\end{pmatrix}\)이고 \(L^{-1}(2, 9, 10) = (2,\ 9 - 2,\ 10 - 9) = (2, 7, 1)\)이다. 흔한 오답은 대각선 아래를 모두 −1로 채우는 것이다. 그 행렬은 \((2, 9, 10)\)을 \((2, 7, -1)\)로 보내고, \(L\)과 곱해도 \(I\)가 아니다.

C2 2차원 차분에서 네 모서리 표시의 부호가 +, −, −, +인 이유와, 가로·세로 누적 순서를 바꿔도 결과가 같은 이유를 행렬로 설명하라.

답: 표시판은 바깥곱 \(x\,\mathbf{u}\mathbf{w}^\top\)이다(\(\mathbf{u} = \mathbf{e}_{r_1} - \mathbf{e}_{r_2+1}\), \(\mathbf{w} = \mathbf{e}_{c_1} - \mathbf{e}_{c_2+1}\)). 칸 값이 \(x\,u_iw_j\)라 부호는 (±1)(±1)의 네 가지 곱이다. 세로 누적은 왼쪽에서 \(L\)을, 가로 누적은 오른쪽에서 \(L^\top\)을 곱하는 일이라 결합법칙으로 순서가 상관없다. 결과 \(x\,(L\mathbf{u})(L\mathbf{w})^\top\)는 행 구간 표시와 열 구간 표시의 바깥곱에 x를 곱한 것, 곧 직사각형 안만 x인 표다. “포함-배제라서”만 답하면 부호는 설명해도 순서를 바꿔도 되는 이유는 빠진다.

C3 누적 최솟값 두 개로 구간 최솟값을 구할 수 없음을 반례로 보이고, 행렬 그림에서 무엇이 없어서인지 말하라.

답: a = [1, 5, 2]와 b = [1, 1, 2]는 앞에서부터의 최솟값이 둘 다 1, 1, 1이다. 그런데 1 ~ 2번의 최솟값은 a에서 2, b에서 1이다. 누적 최솟값 표가 같으니 어떤 계산으로도 둘을 가를 수 없다. 최솟값에는 빼기(되돌리는 계산)가 없어서 \(L^{-1}\)에 해당하는 것이 없기 때문이다.

검증: 비교 표와 대응표의 모든 줄(누적 = \(L\mathbf{a}\), 차분 = \(L^{-1}\mathbf{p}\), 구간 합, 구간 더하기, 선형성, 2차원 바깥곱과 두 누적 순서, 직사각형 합, 한 칸 바꾸기의 영향 범위)을 정수로 맞췄다. 1차원 줄은 무작위 입력 2,000번, 2차원 줄은 500번이다. \(BM = I\), \(MB \ne I\), 0이 아닌 칸 수와 계산 횟수, XOR·나머지 판, 누적 최솟값 반례, float 반올림 반례(구간 합과 차분), 전이 문제(\(F = LQL^\top\), \((L^\top)^{-1} = (L^{-1})^\top\), 분수 계산)와 카드의 값도 계산해 맞췄다. 모두 실험으로 확인한 것이고, 행렬 규칙 자체의 근거는 출처의 교재다 — 37_prefix-sum-triangular_verify.py

  1. Laaksonen, Competitive Programmer’s Handbook (2018년 7월판), 9.1 “Static array queries”(누적 합과 2차원 누적 합), 9.4 “Additional techniques”의 Range updates(원래 배열은 차분 배열의 누적 합이다). ↩

  2. Strang, Introduction to Linear Algebra 5판, 1.3절 “Matrices”(차분 행렬과 합 행렬이 서로의 역행렬이고, 미분·적분과 짝을 이룬다는 예). ↩

  3. P[0]을 붙인 행렬 \(M\), \(B\)와 \(BM = I\), \(MB \ne I\), XOR·나머지 덧셈 판, float 반올림 반례는 교재의 1차원 예를 누적 합과 차분 배열의 표기(P[0] = 0, 길이 n + 1)에 맞춰 넓힌 내용이다. 근거는 37_prefix-sum-triangular_verify.py의 계산이다. ↩

  4. Laaksonen, 같은 책, 9.1의 Minimum queries(최솟값 질문은 합 질문보다 다루기 어렵다), 9.2 “Binary indexed tree”(값을 바꿀 때마다 누적 합 배열을 \(O(n)\)에 다시 만들어야 한다). ↩ ↩2

  5. 2차원 표시를 바깥곱 \(x\,\mathbf{u}\mathbf{w}^\top\)로, 가로·세로 누적을 양쪽에서 곱하는 일로, 직사각형 합을 \((\mathbf{e}_{r_2+1} - \mathbf{e}_{r_1})^\top S\,(\mathbf{e}_{c_2+1} - \mathbf{e}_{c_1})\)로 읽는 것은 교재의 1차원 합 행렬·차분 행렬을 행과 열에 따로 쓴 것이다. 37_prefix-sum-triangular_verify.py에서 무작위 표시판 500개로 확인했다. ↩

  6. Strang, Introduction to Linear Algebra 5판, 2.4절(결합법칙), 2.6절(전진 대입과 연산 수), 2.7절(전치와 곱의 순서). ↩ ↩2

  7. 0이 아닌 칸 수(\(n(n+1)/2\), \(2n - 1\))와 계산 횟수(\(n(n-1)\), \(n - 1\))는 37_prefix-sum-triangular_verify.py에서 \(n \le 40\)까지 세어 확인했다. ↩

  8. 결합 누적분포 \(F(x, y) = \Pr[X \le x, Y \le y]\)의 정의는 Blitzstein·Hwang, Introduction to Probability 2판, 7.1절에 있다. 결합분포와 조건부 기댓값에는 결합 누적분포가 없다. 표의 수는 문제용 예이고, 답은 37_prefix-sum-triangular_verify.py에서 분수로 계산했다. ↩