5.4 ผลรวมสะสม

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

วิธีตรงไปตรงมา

แต่ละคำถาม วนบวกตั้งแต่วัน l ถึงวัน r วันที่ 1 อยู่ช่อง 0 วันที่ day จึงอยู่ช่อง day - 1

#include <stdio.h>

int main()
{
    int steps[100000];
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 0; i < n; i++) {
        scanf("%d", &steps[i]);
    }
    for (int k = 0; k < q; k++) {
        int l, r;
        scanf("%d %d", &l, &r);
        long long total = 0;
        for (int day = l; day <= r; day++) {
            total += steps[day - 1];
        }
        printf("%lld\n", total);
    }
    return 0;
}

7 3
8000 12000 5000 9000 15000 7000 10000
1 7
2 4
5 5

66000
26000
15000

ถูกต้อง แต่ลองนับงาน แต่ละคำถามบวกได้ถึง N ครั้ง Q คำถามจึงบวกได้ถึง N × Q ครั้ง ถ้าโจทย์ให้ N และ Q ถึง 100000 ก็ถึง 10¹⁰ ครั้ง ซึ่งช้าเกินไปมาก วิธีนับงานแบบนี้อย่างเป็นระบบจะเรียนในบทที่ 18

ผลรวมของ i วันแรก

ความคิดหลักคือ คำนวณล่วงหน้าเก็บไว้ในอาเรย์อีกตัวหนึ่ง ให้

อาเรย์ prefix จึงมี N + 1 ช่อง ตั้งแต่ 0 ถึง N และสร้างได้ในลูปเดียว เพราะผลรวมของ i วันแรก คือผลรวมของ i - 1 วันแรก บวกวันที่ i ซึ่งอยู่ช่อง i - 1 ของ steps

prefix[0] = 0;
for (int i = 1; i <= n; i++) {
    prefix[i] = prefix[i - 1] + steps[i - 1];
}

คราวนี้ผลรวมตั้งแต่วัน l ถึงวัน r คือ "ผลรวมของ r วันแรก" ตัดส่วน "l - 1 วันแรก" ทิ้ง

ผลรวมวัน l ถึง r = prefix[r] - prefix[l - 1]

ในภาพ ช่อง prefix[i] วางไว้ตรงรอยต่อหลังวันที่ i เพราะมันคือผลรวมของทุกวันทางซ้ายของรอยต่อนั้น ช่วงวันที่ 2 ถึง 4 อยู่ระหว่างรอยต่อ prefix[1] กับ prefix[4] พอดี

ทำไมต้องมี prefix[0] ลองถามช่วงที่เริ่มจากวันแรก l = 1 สูตรต้องใช้ prefix[0] ถ้าเริ่มอาเรย์ prefix ที่วันแรกเลยโดยไม่มีช่องนี้ ช่วงที่เริ่มวันแรกจะต้องเขียนกรณีพิเศษแยก ช่องที่เป็น 0 ช่องเดียวทำให้สูตรเดียวใช้ได้ทุกช่วง

โปรแกรมเต็ม

#include <stdio.h>

int main()
{
    int steps[100000];
    long long prefix[100001]; // (1)!
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 0; i < n; i++) {
        scanf("%d", &steps[i]);
    }
    prefix[0] = 0;
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + steps[i - 1];
    }
    for (int k = 0; k < q; k++) {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%lld\n", prefix[r] - prefix[l - 1]); // (2)!
    }
    return 0;
}

1. N + 1 ช่อง และเป็น long long เพราะก้าวต่อวันถึง 30000 ร้อยวันก็สามล้าน แสนวันถึงสามพันล้าน เกิน int
2. แต่ละคำถามทำงานแค่ลบหนึ่งครั้ง ไม่มีลูปข้างใน

7 3
8000 12000 5000 9000 15000 7000 10000
1 7
2 4
5 5

66000
26000
15000

ผลตรงกับวิธีตรงไปตรงมาทุกบรรทัด งานทั้งหมดคือสร้าง prefix N ครั้ง กับตอบคำถาม Q ครั้ง รวมแค่ N + Q แทนที่จะเป็น N × Q

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

ทดลองบนโน้ตบุ๊ก AMD Ryzen AI 9 HX 370 แรม 32 GB ใช้ข้อมูลเข้าที่ N = Q = 100000 จำนวนก้าวสุ่ม 0 ถึง 30000 และช่วงคำถามสุ่ม ช่วงทั้งหมดยาวรวมกันประมาณ 2.5 × 10⁹ วัน วิธีตรงไปตรงมาจึงต้องบวกประมาณสองพันห้าร้อยล้านครั้ง รันแต่ละแบบหลายรอบ รอบแรกของแต่ละไฟล์ช้ากว่ารอบอื่นเสมอ ตารางจึงใช้เวลาของรอบหลังๆ ซึ่งได้ใกล้เคียงกันทุกรอบ

โจทย์ที่จำกัดเวลา 1 วินาที วิธีแรกเฉียดขอบหรือไม่ผ่านเลยแล้วแต่เครื่องของ grader และถ้า N กับ Q ใหญ่ขึ้นอีกเท่าตัว งานก็มากขึ้นสี่เท่า ส่วนผลรวมสะสมใช้เวลาเกือบทั้งหมดไปกับการอ่านข้อมูลเข้า การคำนวณแทบไม่กินเวลาเลย

เรื่องผลรวมสะสมยังมีต่อ ผลรวมสะสมของตารางสองมิติอยู่ในหน้า 7.5 ส่วนการใช้คู่กับการค้นหาแบบแบ่งครึ่งอยู่ในบทที่ 19 หน้านี้เป็นแค่จุดเริ่ม

ลองทำให้พัง

แบบที่ 1 ลืมลบหนึ่ง

เขียนสูตรเป็น prefix[r] - prefix[l] เพราะดูสมมาตรกว่า

#include <stdio.h>

int main()
{
    int steps[100000];
    long long prefix[100001];
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 0; i < n; i++) {
        scanf("%d", &steps[i]);
    }
    prefix[0] = 0;
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + steps[i - 1];
    }
    for (int k = 0; k < q; k++) {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%lld\n", prefix[r] - prefix[l]);
    }
    return 0;
}

7 3
8000 12000 5000 9000 15000 7000 10000
1 7
2 4
5 5

58000
14000
0

ทุกคำตอบขาดวัน l ไปหนึ่งวัน เพราะ prefix[l] รวมวันที่ l ไว้แล้ว ลบออกไปเลยหายไปด้วย คำถามที่ l เท่ากับ r ได้ 0 เสมอ ถ้าเจอแบบนี้ ให้ทดสอบกับช่วงยาวหนึ่งวัน คำตอบต้องเท่ากับค่าของวันนั้นพอดี

แบบที่ 2 ใช้ int เก็บผลรวมสะสม

คลิปวิดีโอคลิปหนึ่งมียอดวิวรายวันไม่เกิน 10⁹ ต่อวัน ถามยอดวิวรวมของช่วงวัน ถ้าประกาศ prefix เป็น int

#include <stdio.h>

int main()
{
    int views[100000];
    int prefix[100001];
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 0; i < n; i++) {
        scanf("%d", &views[i]);
    }
    prefix[0] = 0;
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + views[i - 1];
    }
    for (int k = 0; k < q; k++) {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", prefix[r] - prefix[l - 1]);
    }
    return 0;
}

4 4
900000000 800000000 700000000 600000000
1 2
3 4
1 4
2 4

1700000000
1300000000
-1294967296
2100000000

ยอดรวมทั้งสี่วันคือ 3000000000 แต่ได้ค่าติดลบ เพราะ prefix[3] กับ prefix[4] ล้นไปตั้งแต่ตอนสร้าง ที่แปลกคือคำตอบบรรทัดที่ 2 กับ 4 ถูก ทั้งที่ใช้ prefix[4] ที่ล้นไปแล้ว เพราะบนเครื่องที่เขียนเอกสารนี้ ค่าที่ล้นตอนบวกไปวนกลับมาตอนลบพอดี หน้า 1.3 บอกไว้แล้วว่ามาตรฐานภาษา C ไม่รับประกันเรื่องนี้ อย่าพึ่งโชคแบบนี้ ผลรวมสะสมโตได้ถึง N คูณค่ามากสุดเสมอ ให้คิดขนาดจากตรงนั้น ข้อนี้ได้ถึง 10⁵ × 10⁹ = 10¹⁴ ต้องเป็น long long ทั้งอาเรย์และ %lld ตอนพิมพ์

สรุป

• ถามผลรวมช่วงซ้ำหลายครั้ง อย่าบวกใหม่ทุกครั้ง สร้างผลรวมสะสมครั้งเดียว
• prefix[i] คือผลรวมของ i ตัวแรก มี N + 1 ช่อง และ prefix[0] = 0
• สร้างด้วย prefix[i] = prefix[i - 1] + a[i - 1]
• ผลรวมตัวที่ l ถึง r (นับจาก 1) คือ prefix[r] - prefix[l - 1]
• ผลรวมสะสมโตเร็ว ใช้ long long เป็นค่าเริ่มต้น
• ทดสอบด้วยช่วงยาวหนึ่งตัว และช่วงที่เริ่มตัวแรก จะจับการนับเกินหรือขาดหนึ่งได้