19.5 difference array และนับช่วงด้วย prefix sum

หน้า 5.4 กับ 7.5 ใช้ prefix sum ตอบผลรวมของช่วงในเวลาคงที่ หน้านี้ต่อยอดสามทาง ทางแรกกลับด้านกัน คือ บวกค่าให้ทั้งช่วง หลายครั้งแล้วค่อยถามทีหลัง ทางที่สองใช้ความคิดเดิมกับ xor และทางที่สามซึ่งเจอในข้อสอบบ่อยที่สุด คือ นับว่ามีกี่ช่วงที่ผลรวมเท่ากับ k พอดี โดยใช้ prefix sum คู่กับการเรียงและ binary search จากหน้าก่อนๆ

ทบทวนสั้นๆ

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

difference array บวกทั้งช่วง

โรงแรมแห่งหนึ่งเปิดจองล่วงหน้า N คืน มีรายการจอง Q รายการ รายการหนึ่งคือแขก g คนพักตั้งแต่คืนที่ l ถึงคืนที่ r อยากรู้ว่าแต่ละคืนมีแขกพักกี่คน วิธีตรงไปตรงมาคือทุกรายการวนบวก g ให้คืน l ถึง r ซึ่งรายการหนึ่งอาจยาวถึง N คืน รวมเป็น O(NQ)

สังเกตว่ารายการจองหนึ่งรายการ ทำให้จำนวนแขก เปลี่ยน แค่สองจุด คือคืนที่ l มีแขกเพิ่มขึ้น g คน และคืนที่ r + 1 แขกกลุ่มนี้ออกไปแล้ว จึงลดลง g คน ระหว่างนั้นไม่มีอะไรเปลี่ยน ให้จดเฉพาะจุดที่เปลี่ยนลงอาเรย์ diff

diff[l] += g
diff[r + 1] -= g

จดครบทุกรายการแล้ว จำนวนแขกคืนที่ i ก็คือผลรวมของการเปลี่ยนแปลงตั้งแต่คืนแรกถึงคืนที่ i หรือก็คือ prefix sum ของ diff นั่นเอง ลองกับการจอง 4 รายการ ได้แก่ คืน 2 ถึง 4 สามคน คืน 1 ถึง 2 ห้าคน คืน 4 ถึง 7 สองคน และคืน 3 คืนเดียวสี่คน

แถวสุดท้ายคือจำนวนแขกจริงทุกคืน เช่น คืนที่ 2 มีกลุ่มสามคนกับกลุ่มห้าคน รวม 8 คน ช่อง 8 อยู่เลยคืนสุดท้าย มีไว้ให้รายการที่จบคืนที่ 7 ลบได้โดยไม่ต้องเขียนกรณีพิเศษ

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<long long> diff(n + 2, 0); // (1)!
    for (int k = 0; k < q; k++) {
        int l, r, guests;
        cin >> l >> r >> guests;
        diff[l] += guests;
        diff[r + 1] -= guests;
    }
    long long current = 0;
    for (int night = 1; night <= n; night++) {
        current += diff[night]; // (2)!
        cout << current << (night == n ? '\n' : ' ');
    }
    return 0;
}

1. ใช้ช่อง 1 ถึง n + 1 ช่อง n + 1 รับการลบของรายการที่จบคืนสุดท้าย จึงต้องมี n + 2 ช่อง
2. สะสมไปทีละคืน ไม่ต้องเก็บ prefix เป็นอาเรย์อีกตัว เพราะใช้แต่ละค่าครั้งเดียวแล้วพิมพ์เลย

7 4
2 4 3
1 2 5
4 7 2
3 3 4

5 8 7 5 2 2 2

แต่ละรายการใช้งานสองครั้งไม่ว่าช่วงจะยาวแค่ไหน และสะสมอีก N ครั้ง รวมเป็น O(N + Q) diff กับ prefix sum เป็นของตรงข้ามกัน diff[i] คือค่าของคืน i ลบค่าของคืน i - 1 และ prefix sum ของ diff ได้ค่าเดิมกลับมา เหมือนที่ prefix sum ของผลต่างคืนค่าเดิม

ทำแบบเดียวกันในสองมิติได้ ถ้าจะบวก v ให้ทุกช่องในสี่เหลี่ยมมุม (r1, c1) ถึง (r2, c2) ให้บวก v ที่ diff[r1][c1] และ diff[r2 + 1][c2 + 1] ลบ v ที่ diff[r1][c2 + 1] และ diff[r2 + 1][c1] แล้วทำ prefix sum สองมิติตามหน้า 7.5 ทั้งตาราง สังเกตว่าเครื่องหมายของสี่มุมตรงกับสูตรหาผลรวมสี่เหลี่ยมในหน้า 7.5

prefix xor

ความคิดเดียวกันใช้ได้กับ xor ที่เรียนในหน้า 12.3 เพราะ xor มีคุณสมบัติ x ^ x = 0 ถ้าให้ px[i] คือ xor ของ i ตัวแรก แล้ว px[r] ^ px[l - 1] จะหักล้างส่วนของ l - 1 ตัวแรกที่ซ้ำกันออก เหลือ xor ของตัวที่ l ถึง r พอดี เหมือนการลบใน prefix sum เช่น อุปกรณ์ส่งข้อมูลเป็นชุดตัวเลข และใช้ xor ของช่วงเป็นรหัสตรวจสอบ

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> prefix_xor(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int value;
        cin >> value;
        prefix_xor[i] = prefix_xor[i - 1] ^ value;
    }
    for (int k = 0; k < q; k++) {
        int l, r;
        cin >> l >> r;
        cout << (prefix_xor[r] ^ prefix_xor[l - 1]) << '\n';
    }
    return 0;
}

6 4
5 3 7 2 6 4
1 6
2 4
3 3
4 5

1
6
7
4

คำถามที่สองคือ 3 ^ 7 ^ 2 = 6 ต้องมีวงเล็บรอบ ^ ตอนพิมพ์ เพราะ << ทำก่อน ^ เทคนิคนี้ใช้ได้กับการดำเนินการที่ "ถอนกลับได้" อย่างบวกที่ถอนด้วยลบ หรือ xor ที่ถอนด้วยตัวมันเอง แต่ใช้กับค่ามากสุดหรือน้อยสุดไม่ได้ เพราะรู้ค่ามากสุดของ r ตัวแรกกับ l - 1 ตัวแรก ไม่ได้บอกค่ามากสุดของช่วงตรงกลาง

นับช่วงที่ผลรวมเท่ากับ k

ร้านกาแฟจดกำไรรายวัน N วัน วันที่ขาดทุนจดเป็นค่าติดลบ เจ้าของอยากรู้ว่ามีกี่ช่วงวันติดกันที่กำไรรวมเท่ากับ k พอดี วิธีตรงไปตรงมาคือลองทุกคู่ l กับ r แล้วหาผลรวมด้วย prefix sum

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> prefix(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int profit;
        cin >> profit;
        prefix[i] = prefix[i - 1] + profit;
    }
    long long count = 0;
    for (int l = 1; l <= n; l++) {
        for (int r = l; r <= n; r++) {
            if (prefix[r] - prefix[l - 1] == k) {
                count++;
            }
        }
    }
    cout << count << '\n';
    return 0;
}

8 5
3 2 -1 1 5 -5 5 0

11

ถูกต้อง แต่มีคู่ l กับ r ราว N²/2 คู่ เป็น O(N²) ที่ N เป็นแสนไม่ทัน ต้องคิดใหม่จากสูตรผลรวมช่วง

prefix[r] - prefix[l - 1] = k   ก็คือ   prefix[l - 1] = prefix[r] - k

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

ที่ r = 5 prefix[5] คือ 10 ต้องหาค่า 5 ใน j = 0 ถึง 4 เจอที่ j = 2 กับ j = 4 จึงมีสองช่วงที่จบวันที่ 5 คือวันที่ 3 ถึง 5 และวันที่ 5 วันเดียว ทำแบบนี้ครบทุก r แล้วรวมกันได้ 11

ยังเหลือคำถามว่าจะนับเร็วๆ ได้ยังไง กำไรติดลบได้ prefix จึงขึ้นๆ ลงๆ ไม่เรียง ใช้ lower_bound บน prefix ตรงๆ ไม่ได้ มีสองทางตามขอบเขตของโจทย์

ทางที่ 1 ค่าอยู่ในช่วงแคบ ใช้อาเรย์นับ

ถ้าโจทย์บอกว่ากำไรแต่ละวันอยู่ระหว่าง -10 ถึง 10 ค่า prefix ทุกตัวจะอยู่ระหว่าง -10N ถึง 10N เท่านั้น ใช้อาเรย์นับแบบหน้า 5.3 จดว่าค่าแต่ละค่าเคยเป็น prefix มาแล้วกี่ครั้ง ไล่ r จากซ้ายไปขวา ก่อนจดค่าของ r ให้ถามอาเรย์นับว่า prefix[r] - k เคยเจอกี่ครั้ง ซึ่งคือ j ทุกตัวที่น้อยกว่า r พอดี ค่าติดลบใช้เป็น index ไม่ได้ จึงเลื่อนทุกค่าขึ้นด้วย limit แบบที่ทำกับอุณหภูมิติดลบในหน้า 5.3

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long k;
    cin >> n >> k;
    long long limit = 10LL * n;
    vector<int> seen(2 * limit + 1, 0); // (1)!
    long long prefix = 0;
    seen[prefix + limit]++; // (2)!
    long long count = 0;
    for (int i = 1; i <= n; i++) {
        int profit;
        cin >> profit;
        prefix += profit;
        long long want = prefix - k;
        if (want >= -limit && want <= limit) { // (3)!
            count += seen[want + limit];
        }
        seen[prefix + limit]++;
    }
    cout << count << '\n';
    return 0;
}

1. ช่อง v + limit นับว่าค่า v เป็น prefix มาแล้วกี่ครั้ง N เป็นแสน อาเรย์มีราวสองล้านช่อง
2. จด prefix[0] = 0 ไว้ก่อนเริ่ม ช่วงที่เริ่มวันที่ 1 ต้องใช้ค่านี้
3. k อาจใหญ่จน want หลุดช่วงที่อาเรย์รองรับ ค่าแบบนั้นไม่มีทางเป็น prefix ได้ ข้ามไปเลย

8 5
3 2 -1 1 5 -5 5 0

11

ไล่ครั้งเดียว เป็น O(N) แต่ใช้ได้เฉพาะเมื่อช่วงของ prefix แคบพอจะสร้างอาเรย์ ถ้ากำไรแต่ละวันถึง 10⁹ ช่วงของ prefix กว้างถึง 10¹⁴ สร้างอาเรย์ไม่ได้

ทางที่ 2 ค่ากว้าง ใช้การเรียงกับ binary search

เก็บ prefix ทุกตัวเป็นคู่ (ค่า, index) แล้วเรียง pair เรียงตามค่าก่อน ถ้าค่าเท่ากันเรียงตาม index ตามบทที่ 16 คู่ที่มีค่าเท่ากันจึงอยู่ติดกันเป็นกลุ่ม และในกลุ่มเรียงตาม index ด้วย จำนวน j ที่ prefix[j] เท่ากับ want และ j น้อยกว่า r คือระยะระหว่างรอยต่อสองจุดในอาเรย์ที่เรียงแล้ว

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> prefix(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int profit;
        cin >> profit;
        prefix[i] = prefix[i - 1] + profit;
    }
    vector<pair<long long, int>> sorted_prefix(n + 1);
    for (int j = 0; j <= n; j++) {
        sorted_prefix[j] = make_pair(prefix[j], j);
    }
    sort(sorted_prefix.begin(), sorted_prefix.end());
    long long count = 0;
    for (int r = 1; r <= n; r++) {
        long long want = prefix[r] - k;
        auto from = lower_bound(sorted_prefix.begin(), sorted_prefix.end(), make_pair(want, 0)); // (1)!
        auto to = lower_bound(sorted_prefix.begin(), sorted_prefix.end(), make_pair(want, r)); // (2)!
        count += to - from;
    }
    cout << count << '\n';
    return 0;
}

1. คู่แรกที่ไม่น้อยกว่า (want, 0) คือคู่แรกของกลุ่มค่า want เพราะ index ไม่มีทางน้อยกว่า 0
2. คู่แรกที่ไม่น้อยกว่า (want, r) คือคู่แรกในกลุ่มที่ index ตั้งแต่ r ขึ้นไป หรือคู่แรกของกลุ่มถัดไป ระหว่าง from ถึง to จึงเป็นค่า want ที่ index น้อยกว่า r พอดี

8 5
3 2 -1 1 5 -5 5 0

11

เรียงครั้งเดียว O(N log N) แล้วแต่ละ r ค้นสองครั้ง O(log N) รวมเป็น O(N log N) ใช้ได้กับค่าขนาดไหนก็ได้ จำนวนช่วงทั้งหมดมีได้ถึง N(N + 1)/2 ซึ่งเกิน int เมื่อ N เป็นแสน ตัวนับจึงต้องเป็น long long บทที่ 20 จะได้รู้จัก map ที่ทำงานแบบอาเรย์นับในทางที่ 1 ได้กับค่าขนาดไหนก็ได้ และเขียนสั้นกว่านี้

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

วัดบนเครื่องเดียวกับหน้า 19.1 รันแต่ละแบบ 5 รอบ ตารางแรกคือโรงแรม N = 100000 คืน รายการจอง Q = 100000 รายการ ช่วงสุ่ม ยาวเฉลี่ยราวหนึ่งในสามของทั้งหมด วิธีตรงไปตรงมาจึงบวกราว 3 × 10⁹ ครั้ง

ลูปบวกช่วงต่อเนื่องเป็นงานที่ -O2 เร่งได้มาก เพราะ compiler สั่งให้บวกหลายช่องพร้อมกันได้ วิธีตรงไปตรงมาแบบ -O2 จึงยังอยู่ในหนึ่งวินาที แต่ถ้า N กับ Q เพิ่มเป็นสองแสน งานจะเพิ่มสี่เท่าและเกินทันที ส่วน difference array เร็วเท่าการอ่านข้อมูล

ตารางที่สองคือนับช่วงที่ผลรวมเท่ากับ 7 กำไรรายวันสุ่มตั้งแต่ -10 ถึง 10 ซึ่งใช้ได้ทั้งสามวิธี

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

ลองทำให้พัง

แบบที่ 1 ลบที่ r แทน r + 1

ในโปรแกรม hotel เขียน diff[r] -= guests; เพราะคิดว่าแขกพักถึงคืน r ก็ควรลบที่ r

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<long long> diff(n + 2, 0);
    for (int k = 0; k < q; k++) {
        int l, r, guests;
        cin >> l >> r >> guests;
        diff[l] += guests;
        diff[r] -= guests;
    }
    long long current = 0;
    for (int night = 1; night <= n; night++) {
        current += diff[night];
        cout << current << (night == n ? '\n' : ' ');
    }
    return 0;
}

7 4
2 4 3
1 2 5
4 7 2
3 3 4

5 3 3 2 2 2 0

ทุกรายการหายไปหนึ่งคืนท้าย และรายการที่จองคืนเดียว (คืน 3 สี่คน) หายไปทั้งรายการ เพราะบวกแล้วลบที่ช่องเดียวกัน diff[i] คือการเปลี่ยนแปลงตอน เริ่ม คืนที่ i แขกยังอยู่ตลอดคืน r จึงต้องลดตอนเริ่มคืน r + 1 ทดสอบ difference array ด้วยช่วงยาวหนึ่งเสมอ เหมือนที่หน้า 5.4 ทดสอบ prefix sum ด้วยช่วงยาวหนึ่ง

แบบที่ 2 ลืม prefix[0]

ในโปรแกรม sum-k-sorted เก็บเฉพาะ prefix[1] ถึง prefix[n] ลงในอาเรย์ที่จะเรียง เพราะคิดว่า prefix[0] เป็นแค่ 0 ไม่ใช่ของจริง

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> prefix(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int profit;
        cin >> profit;
        prefix[i] = prefix[i - 1] + profit;
    }
    vector<pair<long long, int>> sorted_prefix(n);
    for (int j = 1; j <= n; j++) {
        sorted_prefix[j - 1] = make_pair(prefix[j], j);
    }
    sort(sorted_prefix.begin(), sorted_prefix.end());
    long long count = 0;
    for (int r = 1; r <= n; r++) {
        long long want = prefix[r] - k;
        auto from = lower_bound(sorted_prefix.begin(), sorted_prefix.end(), make_pair(want, 0));
        auto to = lower_bound(sorted_prefix.begin(), sorted_prefix.end(), make_pair(want, r));
        count += to - from;
    }
    cout << count << '\n';
    return 0;
}

8 5
3 2 -1 1 5 -5 5 0

8

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

สรุป

• บวก g ให้ช่วง l ถึง r หลายครั้ง จดแค่ diff[l] += g กับ diff[r + 1] -= g แล้วทำ prefix sum ครั้งเดียว ได้ O(N + Q)
• xor ของช่วงคือ px[r] ^ px[l - 1] ใช้ได้กับการดำเนินการที่ถอนกลับได้เท่านั้น ใช้กับค่ามากสุดไม่ได้
• ช่วงที่ผลรวมเท่ากับ k คือคู่ j < r ที่ prefix[j] = prefix[r] - k นับด้วยอาเรย์นับเมื่อค่าแคบ หรือเรียงคู่ (ค่า, index) แล้วใช้ lower_bound สองครั้งเมื่อค่ากว้าง
• อย่าลืม prefix[0] = 0 และทดสอบด้วยช่วงยาวหนึ่ง กับช่วงที่เริ่มตัวแรก

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