Tổng khối con

Hướng tiếp cận

Bài toán là mở rộng tự nhiên của kỹ thuật prefix sum (tổng tiền tố) từ một chiều và hai chiều lên ba chiều. Với mỗi truy vấn ta cần tính tổng các phần tử trong một hộp chữ nhật. Nếu duyệt trực tiếp thì độ phức tạp là $O(q·X·Y·Z)$, có thể lên tới $2·{10}^{11}$ phép cộng — không đạt yêu cầu.

Ta tiền xử lý mảng tổng tiền tố 3 chiều $S$ rồi mỗi truy vấn chỉ cần $O(1)$.

Nhận xét quan trọng

1. Định nghĩa $S[i][j][k]$ là tổng của tất cả $A[i^{\prime }][j^{\prime }][k^{\prime }]$ với $1\le i^{\prime }\le i$, $1\le j^{\prime }\le j$, $1\le k^{\prime }\le k$ (quy ước $S=0$ nếu một chỉ số là $0$).
2. Theo nguyên lý bao hàm – loại trừ trong không gian 3 chiều, hộp $[1..i]\times [1..j]\times [1..k]$ có thể được phân tích qua các hộp con trừ phần giao nhau ba mặt.
3. Bộ nhớ: vì $X·Y·Z\le {10}^6$, ta dùng một mảng phẳng 1 chiều với chỉ số $i·(Y+1)(Z+1)+j·(Z+1)+k$ để tiết kiệm cấp phát.

Thuật toán

Xây dựng $S$. Khởi tạo $S$ là mảng $(X+1)(Y+1)(Z+1)$ giá trị $0$, sau đó với mọi $1\le i\le X$, $1\le j\le Y$, $1\le k\le Z$:

$$S[i][j][k]=A[i][j][k]+S[i-1][j][k]+S[i][j-1][k]+S[i][j][k-1]$$ $$-S[i-1][j-1][k]-S[i-1][j][k-1]-S[i][j-1][k-1]+S[i-1][j-1][k-1].$$

Trả lời truy vấn. Với truy vấn $(x_1,y_1,z_1,x_2,y_2,z_2)$:

$$\text{ans}=S[x_2][y_2][z_2]-S[x_1-1][y_2][z_2]-S[x_2][y_1-1][z_2]-S[x_2][y_2][z_1-1]$$ $$+S[x_1-1][y_1-1][z_2]+S[x_1-1][y_2][z_1-1]+S[x_2][y_1-1][z_1-1]-S[x_1-1][y_1-1][z_1-1].$$

Quy luật dấu: với $t$ là số chỉ số bị giảm xuống $-1$ (tức dùng $x_1-1$, $y_1-1$, hoặc $z_1-1$), hệ số là $(-1{)}^t$. Tổng cộng có $2^3=8$ số hạng.

Lưu ý cài đặt.

• Dùng long long vì tổng có thể đạt ${10}^6·{10}^9={10}^{15}$.
• Đọc/xuất I/O nhanh (scanf/printf hoặc sys.stdin.read cho Python).
• Mảng phẳng 1 chiều giúp truy cập cache thân thiện và tránh nhiều lần cấp phát.

Độ phức tạp

• Thời gian: $O(X·Y·Z+q)$.
• Bộ nhớ: $O(X·Y·Z)$.