7.5 ผลรวมสะสมสองมิติ

ในหน้า 5.4 เราใช้ผลรวมสะสม (prefix sum) ตอบคำถาม "ผลรวมตั้งแต่ตัวที่ l ถึงตัวที่ r" ได้ทันทีโดยไม่ต้องบวกใหม่ทุกครั้ง หน้านี้ขยายความคิดเดียวกันไปเป็นตาราง เพื่อตอบคำถาม "ผลรวมในสี่เหลี่ยมนี้" ได้ทันที โจทย์แนวนี้ให้คำถามมาเป็นแสนข้อ วิธีบวกทีละช่องจะช้าเกินเวลา

โจทย์ผลรวมในสี่เหลี่ยม

ทุ่งนาแบ่งเป็นแปลง R แถว C คอลัมน์ แต่ละแปลงรู้ผลผลิตเป็นกิโลกรัม มีคำถาม Q ข้อ แต่ละข้อบอกมุมบนซ้าย (r1, c1) กับมุมล่างขวา (r2, c2) ของสี่เหลี่ยม ให้ตอบผลผลิตรวมของทุกแปลงในสี่เหลี่ยมนั้น แถวและคอลัมน์ในโจทย์นับจาก 1

หน้านี้ เก็บตารางตั้งแต่แถว 1 คอลัมน์ 1 ให้ตรงกับโจทย์ แถว 0 กับคอลัมน์ 0 ปล่อยว่างไว้เป็น 0 จึงประกาศขนาด [1001][1001] สำหรับ R และ C ไม่เกิน 1000 เหตุผลที่ต้องมีแถว 0 จะเห็นตอนสร้างตาราง

วิธีตรงไปตรงมาคือบวกทุกช่องในสี่เหลี่ยมทุกครั้งที่ถาม

#include <stdio.h>

int field[1001][1001];

int main()
{
    int rows, cols;
    scanf("%d %d", &rows, &cols);
    for (int r = 1; r <= rows; r++) {
        for (int c = 1; c <= cols; c++) {
            scanf("%d", &field[r][c]);
        }
    }
    int questions;
    scanf("%d", &questions);
    for (int i = 0; i < questions; i++) {
        int r1, c1, r2, c2;
        scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
        long long sum = 0;
        for (int r = r1; r <= r2; r++) {
            for (int c = c1; c <= c2; c++) {
                sum += field[r][c];
            }
        }
        printf("%lld\n", sum);
    }
    return 0;
}

3 4
5 2 7 1
0 9 3 4
8 6 2 6
3
1 1 3 4
2 2 3 3
1 4 3 4

53
20
11

คำตอบถูก แต่ถ้า R และ C เป็น 1000 และสี่เหลี่ยมใหญ่เกือบเต็มทุ่ง คำถามหนึ่งข้อต้องบวกเกือบล้านครั้ง Q เป็นแสนข้อคือราวแสนล้านครั้ง ไม่มีทางทันเวลา 1 วินาที

ความคิด เก็บผลรวมจากมุมบนซ้าย

ให้ prefix[i][j] คือผลรวมของสี่เหลี่ยมตั้งแต่มุมบนซ้าย (1, 1) ถึงช่อง (i, j) ถ้ามีตารางนี้แล้ว ทุกคำถามตอบได้ด้วยการบวกลบแค่สี่ค่า ไม่ว่าสี่เหลี่ยมจะใหญ่แค่ไหน

สร้างตาราง prefix

ไล่ทีละช่องจากบนลงล่าง ซ้ายไปขวา ตอนคิดช่อง (i, j) ช่องข้างบนและข้างซ้ายคิดเสร็จไปแล้ว เอามาประกอบกันได้

• prefix[i-1][j] คือส่วนบน ทุกแถวเหนือแถว i ตั้งแต่คอลัมน์ 1 ถึง j
• prefix[i][j-1] คือส่วนซ้าย ทุกคอลัมน์ทางซ้ายของคอลัมน์ j ตั้งแต่แถว 1 ถึง i
• สองส่วนนี้ซ้อนกันตรงมุมบนซ้าย prefix[i-1][j-1] บวกสองส่วนแล้วมุมนี้ถูกนับสองครั้ง ต้องลบออกหนึ่งครั้ง
• ขาดแค่ช่อง (i, j) เอง บวกเข้าไป

prefix[i][j] = field[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]

การบวกสองส่วนที่ซ้อนกันแล้วลบส่วนที่ซ้อนออก มีชื่อเรียกว่า หลักการเพิ่มเข้าตัดออก (inclusion-exclusion) ตอนคิดแถว 1 จะต้องใช้ prefix[0][j] และตอนคิดคอลัมน์ 1 จะต้องใช้ prefix[i][0] นี่คือเหตุผลที่เก็บตารางตั้งแต่ 1 แถว 0 กับคอลัมน์ 0 เป็น 0 อยู่แล้ว สูตรเดียวจึงใช้ได้ทุกช่อง ไม่ต้องมี if แยกกรณีขอบ

#include <stdio.h>

int field[1001][1001];
long long prefix[1001][1001];

int main()
{
    int rows, cols;
    scanf("%d %d", &rows, &cols);
    for (int r = 1; r <= rows; r++) {
        for (int c = 1; c <= cols; c++) {
            scanf("%d", &field[r][c]);
        }
    }
    for (int r = 1; r <= rows; r++) {
        for (int c = 1; c <= cols; c++) {
            prefix[r][c] = field[r][c] + prefix[r - 1][c] + prefix[r][c - 1] - prefix[r - 1][c - 1];
        }
    }
    for (int r = 1; r <= rows; r++) {
        for (int c = 1; c <= cols; c++) {
            printf("%3lld", prefix[r][c]);
        }
        printf("\n");
    }
    return 0;
}

3 4
5 2 7 1
0 9 3 4
8 6 2 6

  5  7 14 15
  5 16 26 31
 13 30 42 53

%3lld จัดให้ตัวเลขกว้าง 3 ช่องตามบทที่ 2 จะได้อ่านเป็นตารางง่าย ลองตรวจช่องแถว 2 คอลัมน์ 2 ด้วยมือ 9 + 7 + 5 - 5 = 16 ตรงกับผลรวมจริงของ 5 2 0 9 และช่องล่างขวาสุด 53 คือผลรวมทั้งตาราง

prefix เป็น long long เพราะผลรวมของทั้งตารางใหญ่ได้ถึง R × C เท่าของค่ามากสุด ตาราง 1000 × 1000 ที่ช่องละ 10⁴ รวมได้ถึง 10¹⁰ เกิน int

ตอบผลรวมในสี่เหลี่ยม

สี่เหลี่ยม (r1, c1) ถึง (r2, c2) คิดย้อนแบบเดียวกัน เริ่มจากก้อนใหญ่ prefix[r2][c2] ที่มีส่วนเกินอยู่ทางบนและทางซ้าย ตัดสองส่วนนั้นออก แล้วบวกมุมบนซ้ายที่ถูกตัดซ้ำสองครั้งคืน

sum = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1]

เมื่อ r1 เป็น 1 จะได้ prefix[0][...] ซึ่งเป็น 0 ไม่มีส่วนบนให้ตัด สูตรยังถูกโดยไม่ต้องแยกกรณี รวมเป็นโปรแกรมเต็มได้ดังนี้ สร้าง prefix ไปพร้อมกับตอนอ่าน เพราะตอนอ่านช่อง (r, c) ช่องข้างบนและข้างซ้ายถูกอ่านมาแล้ว

#include <stdio.h>

int field[1001][1001];
long long prefix[1001][1001];

int main()
{
    int rows, cols;
    scanf("%d %d", &rows, &cols);
    for (int r = 1; r <= rows; r++) {
        for (int c = 1; c <= cols; c++) {
            scanf("%d", &field[r][c]);
            prefix[r][c] = field[r][c] + prefix[r - 1][c] + prefix[r][c - 1] - prefix[r - 1][c - 1];
        }
    }
    int questions;
    scanf("%d", &questions);
    for (int i = 0; i < questions; i++) {
        int r1, c1, r2, c2;
        scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
        long long sum = prefix[r2][c2] - prefix[r1 - 1][c2] - prefix[r2][c1 - 1] + prefix[r1 - 1][c1 - 1]; // (1)!
        printf("%lld\n", sum);
    }
    return 0;
}

1. คำถามหนึ่งข้อบวกลบแค่สี่ค่า ไม่มีลูป สี่เหลี่ยมเล็กหรือใหญ่ใช้เวลาเท่ากัน

3 4
5 2 7 1
0 9 3 4
8 6 2 6
3
1 1 3 4
2 2 3 3
1 4 3 4

53
20
11

คำถามที่สองคิดด้วยมือได้ 42 - 14 - 13 + 5 = 20 ตรงกับ 9 + 3 + 6 + 2

เร็วขึ้นแค่ไหน

วัดบนโน้ตบุ๊ก AMD Ryzen AI 9 HX 370 กับ Windows 11 และ GCC 14.2 ของ Code::Blocks ตารางขนาด 1000 × 1000 ค่าในช่องสุ่มตั้งแต่ 0 ถึง 1000 มีคำถาม 100000 ข้อ ชุดแรกสุ่มสี่เหลี่ยมขนาดไหนก็ได้ ชุดที่สองทุกคำถามเป็นสี่เหลี่ยมใหญ่ มุมบนซ้ายอยู่ในแถวและคอลัมน์ 1 ถึง 100 มุมล่างขวาอยู่ใน 901 ถึง 1000 เวลานับรวมการอ่านข้อมูลเข้าราว 5.5 MB และการพิมพ์คำตอบแล้ว

วิธีบวกทีละช่องช้าขึ้นตามขนาดของสี่เหลี่ยม ส่วน prefix ใช้เวลาเกือบเท่าเดิมทั้งสองชุด เวลาเกือบทั้งหมดของ prefix คือการอ่านตัวเลขล้านตัว ไม่ใช่การคำนวณ ราคาที่จ่ายคือหน่วยความจำของตาราง prefix อีกหนึ่งตาราง ตาราง long long ขนาด 1001 × 1001 ใช้ราว 8 MB ซึ่งไม่มีปัญหาเมื่อประกาศไว้นอก main

ลองทำให้พัง

แบบที่ 1 ลืมบวกมุมคืน

ในโปรแกรม prefix เขียนสูตรคำตอบขาดพจน์สุดท้าย

long long sum = prefix[r2][c2] - prefix[r1 - 1][c2] - prefix[r2][c1 - 1];

คอมไพล์ผ่าน รันกับข้อมูลเข้าชุดเดิมได้

53
15
11

ผิดแค่คำถามที่สอง คำถามแรกกับคำถามที่สามมี r1 เป็น 1 มุมที่ลืมบวกคืนคือ prefix[0][...] ซึ่งเป็น 0 อยู่แล้ว จึงบังเอิญถูก ถ้าทดสอบแค่สี่เหลี่ยมที่เริ่มจากขอบบนหรือขอบซ้าย จะไม่มีวันเห็นบั๊กนี้ ทดสอบด้วยสี่เหลี่ยมที่อยู่กลางตารางเสมอ

แบบที่ 2 ตาราง prefix เป็น int

ค่าในแต่ละช่องเก็บใน int ได้สบาย หลายคนจึงประกาศ prefix เป็น int ตามไปด้วย ลองกับโจทย์ที่ค่าในช่องถึง 10⁹

#include <stdio.h>

int field[1001][1001];
int prefix[1001][1001];

int main()
{
    int rows, cols;
    scanf("%d %d", &rows, &cols);
    for (int r = 1; r <= rows; r++) {
        for (int c = 1; c <= cols; c++) {
            scanf("%d", &field[r][c]);
            prefix[r][c] = field[r][c] + prefix[r - 1][c] + prefix[r][c - 1] - prefix[r - 1][c - 1];
        }
    }
    int questions;
    scanf("%d", &questions);
    for (int i = 0; i < questions; i++) {
        int r1, c1, r2, c2;
        scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
        long long sum = prefix[r2][c2] - prefix[r1 - 1][c2] - prefix[r2][c1 - 1] + prefix[r1 - 1][c1 - 1];
        printf("%lld\n", sum);
    }
    return 0;
}

2 2
1000000000 1000000000
1000000000 1000000000
2
1 1 1 2
1 1 2 2

2000000000
-294967296

คำถามแรกถูก เพราะผลรวมของสองช่องคือสองพันล้าน ยังไม่เกิน int แต่ผลรวมทั้งสี่ช่องคือสี่พันล้าน prefix[2][2] ล้นไปตั้งแต่ตอนสร้างตาราง คำตอบจึงติดลบ ตัวแปร sum เป็น long long ก็ช่วยไม่ได้ เพราะค่าที่เอามาบวกลบผิดไปก่อนแล้ว เหมือนกับดัก int คูณ int ในหน้า 1.3 ค่าในช่องเล็กไม่ได้แปลว่าผลรวมจะเล็ก ให้คิดจากผลรวมทั้งตาราง คือ R × C × ค่ามากสุด

สรุป

• prefix[i][j] คือผลรวมจากมุมบนซ้าย (1, 1) ถึง (i, j)
• สร้างด้วย field[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]
• ตอบด้วย prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1] คำถามละสี่ค่า ไม่มีลูป
• เก็บตารางตั้งแต่ 1 ให้แถว 0 กับคอลัมน์ 0 เป็นศูนย์ สูตรเดียวใช้ได้ทุกช่อง
• ใช้ long long กับตาราง prefix และทดสอบด้วยสี่เหลี่ยมกลางตาราง

กลับไปเช็กรายการ ผ่านบทนี้เมื่อ แล้วไปทำแบบฝึกหัด