ปูพื้นฐาน

ผลรวมสะสมกับต้นไม้เฟนวิก: ตอบคำถามช่วงได้ทันที แม้ข้อมูลจะถูกแก้ระหว่างทาง

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

อาการ · คำถามเดียวกันที่ถูกถามสองแสนครั้ง

โจทย์ชุดหนึ่งที่โผล่บ่อยมากหน้าตาเป็นแบบนี้ ให้อาเรย์ยาว n ตัว แล้วมีคำถามตามมาอีก q ข้อ แต่ละข้อถามว่า "ผลรวมของช่องที่ l ถึงช่องที่ r เป็นเท่าไร" ตอบให้ครบทุกข้อ

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

บทนี้ไล่จากท่าที่ง่ายที่สุดไปหาท่าที่ยืดหยุ่นที่สุด แล้วจบด้วยคำถามที่สำคัญกว่าทั้งสองท่า คือเมื่อไรควรใช้อันไหน เพราะท่าที่แรงกว่าไม่ได้แปลว่าท่าที่ควรหยิบ

ลองเอง · ตอบผลรวมของช่วงให้ทัน

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

ท่าที่หนึ่ง · ผลรวมสะสม

แทนที่จะตอบคำถามตอนถูกถาม ให้ทำการบ้านไว้ก่อนหนึ่งรอบ สร้างอาเรย์ใหม่ชื่อ pre ที่ pre[i] เก็บผลรวมตั้งแต่ช่องแรกจนถึงช่องที่ i เรียกมันว่า ผลรวมสะสม (prefix sum) คำว่า prefix อ่านว่า "พรีฟิกซ์" แปลว่าส่วนที่นำหน้า เป็นคำเดียวกับคำนำหน้าคำในภาษาอังกฤษ ที่นี่หมายถึงท่อนที่เริ่มจากหัวแถวเสมอ

พอมีตารางนี้แล้ว ผลรวมของช่วงใด ๆ ก็หักลบกันออกมาได้ในการคำนวณครั้งเดียว

เอาอาเรย์ตัวอย่าง 3 1 4 1 5 9 2 6 มาไล่ให้เห็นชัด ๆ

ท่านี้จบเร็วและเขียนสั้นมาก ปัญหาเดียวของมันโผล่ตอนโจทย์เติมประโยคเดียวเข้ามาว่า "ระหว่างทางมีการแก้ค่าในช่องด้วย" เพราะการแก้ค่าช่องที่ 3 ทำให้ pre[3] จนถึง pre[n] ผิดหมดทุกช่อง ต้องสร้างใหม่ทั้งแถว

// ผลรวมสะสม สร้างครั้งเดียวแล้วตอบทุกช่วงในเวลาคงที่
// pre[0] = 0 เสมอ เพื่อให้ช่วงที่เริ่มที่ 1 ไม่ต้องเขียนเงื่อนไขพิเศษ
vector<long long> pre(n + 1, 0);
for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];

long long sum = pre[r] - pre[l - 1];   // ผลรวมของ a[l..r]

ท่าที่สอง · ต้นไม้เฟนวิก

โครงสร้างที่ตอบคำถามข้างบนชื่อ ต้นไม้เฟนวิก (Fenwick tree) อ่านว่า "เฟนวิก" ตั้งตามชื่อ Peter Fenwick นักวิทยาศาสตร์คอมพิวเตอร์ชาวนิวซีแลนด์ที่เขียนถึงมันในปี 1994 อีกชื่อที่เจอบ่อยพอกันคือ Binary Indexed Tree (ย่อว่า BIT) แปลตรงตัวว่าต้นไม้ที่ใช้เลขฐานสองเป็นดัชนี ซึ่งเป็นชื่อที่บอกกลไกได้ตรงกว่า

กติกามีข้อเดียว ช่องที่ i ของต้นไม้ดูแลช่วงที่ยาวเท่ากับบิตต่ำสุดที่ยังเป็น 1 ของ i และช่วงนั้นจบลงที่ i พอดี เขียนบิตต่ำสุดนั้นเป็นสูตรได้ว่า i & -i

เหตุผลที่ i & -i ให้บิตต่ำสุดออกมา อยู่ที่วิธีที่คอมพิวเตอร์เก็บเลขติดลบ ค่า -i คือการกลับบิตทุกตัวของ i แล้วบวกหนึ่ง ผลคือบิตทางซ้ายของบิตต่ำสุดกลับด้านกันหมด และบิตต่ำสุดเองยังตรงกัน การ and กันจึงเหลือรอดแค่บิตเดียวนั้น

หัวตารางคือค่าประจำหลัก ไม่ใช่ลำดับหลัก จะได้อ่านคำตอบของแถวล่างสุดออกมาเป็นเลขได้เลย

ลองเอง · ต่อก้อนให้เต็มช่วง

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

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

ถามผลรวม · ตัดทีละก้อนจากขวาเข้าซ้าย

อยากได้ผลรวมตั้งแต่ต้นถึงตำแหน่ง 7 ก็เริ่มที่ช่อง t[7] ซึ่งดูแลช่วงท้ายสุดมาก้อนหนึ่ง แล้วกระโดดถอยไปยังช่องที่ดูแลก้อนถัดไป การกระโดดคือ i -= i & -i ตรง ๆ ทำซ้ำจนถึงศูนย์

สามก้อนนี้ต่อกันพอดีเป็นช่วง a[1..7] ไม่ทับกันและไม่มีรู ผลรวมที่ได้คือ 25 ตรงกับ pre[7] ในตารางแรก ที่มันแวะแค่ 3 ช่องเพราะเลข 7 เขียนฐานสองได้ 111 ซึ่งมีเลขหนึ่งอยู่ 3 ตัว และการกระโดดหนึ่งครั้งลบเลขหนึ่งออกไปหนึ่งตัวเสมอ

แก้ค่า · ไล่ขึ้นไปหาทุกช่องที่ครอบเราอยู่

ถ้าค่าที่ตำแหน่ง 3 เปลี่ยนไป ช่องของต้นไม้ที่ต้องแก้ตามคือทุกช่องที่ช่วงของมันคลุมตำแหน่ง 3 อยู่ ซึ่งหาได้ด้วยการกระโดดไปทางตรงข้ามคือ i += i & -i

ช่องอื่นที่เหลือทั้งหมดไม่มีตำแหน่ง 3 อยู่ในช่วงของมัน จึงไม่ต้องแตะเลย จาก 8 ช่องเหลือแก้แค่ 3 ช่อง และพอ n เป็นสองแสน ตัวเลขนี้ก็ยังไม่เกิน 18

เขียนเป็นโค้ด

ทั้งโครงสร้างยาวไม่ถึงยี่สิบบรรทัด และสองลูปในนั้นต่างกันแค่เครื่องหมายบวกกับลบเท่านั้น

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

// ต้นไม้เฟนวิก ดัชนีเริ่มที่ 1 เสมอ เพราะสูตร i & -i ใช้กับ 0 ไม่ได้ (วนไม่รู้จบ)
struct BIT {
    int n;
    vector<long long> t;
    BIT(int n_) : n(n_), t(n_ + 1, 0) {}

    // บวก v เข้าไปที่ตำแหน่ง i แล้วไล่ขึ้นไปแก้ทุกช่องที่ครอบ i อยู่
    void add(int i, long long v) {
        for (; i <= n; i += i & -i) t[i] += v;
    }

    // ผลรวมตั้งแต่ตำแหน่ง 1 ถึง i โดยไล่ตัดทีละก้อนจากขวาเข้าซ้าย
    long long pre(int i) {
        long long s = 0;
        for (; i > 0; i -= i & -i) s += t[i];
        return s;
    }

    long long range(int l, int r) { return pre(r) - pre(l - 1); }
};

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    BIT b(n);
    vector<long long> a(n + 1, 0);
    for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); b.add(i, a[i]); }

    while (q--) {
        int op;
        scanf("%d", &op);
        if (op == 1) {                     // แก้ค่าที่ตำแหน่ง i ให้เป็น v
            int i; long long v;
            scanf("%d %lld", &i, &v);
            b.add(i, v - a[i]);            // ส่ง "ส่วนต่าง" เข้าไป ไม่ใช่ค่าใหม่
            a[i] = v;
        } else {                           // ถามผลรวมของช่วง [l, r]
            int l, r;
            scanf("%d %d", &l, &r);
            printf("%lld\n", b.range(l, r));
        }
    }
    return 0;
}

ผมสุ่มเทียบกับตัวไล่บวกทีละช่องแบบซื่อ ๆ 400 เทส แต่ละเทสสุ่มทั้งการถามและการแก้ค่าสลับกันไปมา รวมทั้งกรณี n = 1 และค่าติดลบ ตรงกันทั้งหมด

ข้อจำกัด · สิ่งเดียวที่เฟนวิกขอจากเราเป็นการแลก

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

ทางออกที่บทนี้ใช้ตั้งแต่ต้นคือไม่ต่อช่วงกลางตาราง แต่เอาสองช่วงหัวแถวมาหักกัน คือ range(l, r) = pre(r) − pre(l − 1) ซึ่งเป็นบรรทัดที่ดูไม่มีอะไรเลยในโค้ด แต่มันคือที่ที่ข้อจำกัดทั้งหมดของเฟนวิกซ่อนอยู่ เพราะการหักกันได้แปลว่าตัวดำเนินการที่ใช้ต้องมี ตัวผกผัน (inverse อ่านว่า "อินเวิร์ส" แปลว่าตัวที่ย้อนของเดิมกลับ เหมือนการลบที่ย้อนการบวก)

เทคนิคอื่นในกล่องเดียวกัน

สี่ท่าถัดไปเป็นของที่ต่อยอดจากสองลูปเดิมโดยไม่ต้องเปลี่ยนโครงสร้างเลย ผมยกมาจาก หน้า Fenwick Tree ของ cp-algorithms ซึ่งเป็นแหล่งอ้างอิงที่ครบที่สุดของหัวข้อนี้ แล้วเขียนโค้ดใหม่ในสไตล์เดียวกับบทนี้ ทุกชิ้นคอมไพล์แล้วสุ่มเทียบกับตัวไล่ตรง ๆ 3 000 รอบ รอบละสุ่มทั้งขนาดอาเรย์ คำสั่ง และค่าติดลบ ตรงกันทุกรอบ

ท่าที่ 1 · สร้างต้นไม้ในเวลา O(n)

โค้ดหลักของบทนี้สร้างต้นไม้ด้วยการเรียก add ทีละช่อง n ครั้ง ซึ่งเป็น n log n ทั้งที่มันเป็นงานเชิงเส้นได้ ท่าที่เร็วกว่าคือยกยอด เอาอาเรย์ต้นฉบับมาเป็นต้นไม้เลย แล้วเดินไปข้างหน้าครั้งเดียว ช่องไหนเสร็จแล้วก็โยนยอดรวมของตัวเอง ขึ้นไปให้ช่องที่ครอบมันอยู่ ทุกช่องจึงถูกแตะสองครั้งเท่านั้น

// สร้างต้นไม้ในเวลา O(n) แทนที่จะเรียก add ทีละช่อง n log n ครั้ง
// เวอร์ชันนี้เขียนแบบฐานศูนย์ เพราะสูตรที่ใช้คือ i | (i+1) ไม่ใช่ i & -i
// (ทั้งสองแบบคือของอย่างเดียวกัน แค่เลื่อนดัชนีไปหนึ่ง)
vector<long long> b = a;                  // ยืมอาเรย์ต้นฉบับมาเป็นต้นไม้เลย
for (int i = 0; i < n; i++) {
    int r = i | (i + 1);                  // ช่องถัดไปที่ครอบ i อยู่
    if (r < n) b[r] += b[i];              // ยกยอดของช่องนี้ขึ้นไปให้ช่องที่ครอบ
}

// ถามผลรวม 0..i ของเวอร์ชันฐานศูนย์ ตัดก้อนด้วย (i & (i+1)) - 1
long long pre(int i) {
    long long s = 0;
    for (; i >= 0; i = (i & (i + 1)) - 1) s += b[i];
    return s;
}

ท่าที่ 2 · แก้เป็นช่วง ถามเป็นจุด

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

// แก้ค่าเป็นช่วง ถามค่าเป็นจุด ใช้ต้นไม้ใบเดียว
// กลไกคือเก็บ "ส่วนต่างระหว่างช่องกับช่องก่อนหน้า" แทนที่จะเก็บตัวค่า
// พอถามจุด i ก็คือบวกส่วนต่างทั้งหมดตั้งแต่หัวแถว ซึ่งเป็นงานที่ต้นไม้ทำอยู่แล้ว
void addRange(int l, int r, long long v) {
    add(l, v);                 // ตั้งแต่ช่อง l เป็นต้นไป สูงขึ้น v
    if (r + 1 <= n) add(r + 1, -v);   // พ้นช่อง r แล้ว หักคืน v ให้กลับเป็นเดิม
}

long long at(int i) { return pre(i); }   // ค่าที่ตำแหน่ง i คือผลรวมของส่วนต่าง

ท่าที่ 3 · แก้เป็นช่วง ถามเป็นช่วง

ท่าที่ 2 ตอบจุดเดียวได้แต่ตอบช่วงไม่ได้ ถ้าอยากได้ทั้งสองอย่างต้องใช้ต้นไม้สองใบ ใบแรกเก็บส่วนต่างเหมือนเดิม ปัญหาคือ b1.pre(i) * i คิดเหมือนว่าของที่เพิ่มเข้ามา เริ่มนับตั้งแต่ช่องแรก ซึ่งเกินความจริงไปเท่ากับ v * (l − 1) ทุกครั้ง ต้นไม้ใบที่สองจึงมีหน้าที่เดียวคือจดส่วนเกินนั้นไว้ให้หักคืน

ตรวจสามช่วงด้วยมือจะเห็นว่ามันลงตัว ตำแหน่งก่อน l ทั้งสองพจน์เป็นศูนย์ ตำแหน่งในช่วงได้ v คูณจำนวนช่องที่นับมาแล้ว และตำแหน่งหลัง r ได้ v คูณความยาวช่วงเต็มพอดี

// แก้เป็นช่วง ถามเป็นช่วง ใช้ต้นไม้สองใบ
// b1 เก็บส่วนต่างเหมือนหัวข้อก่อน ส่วน b2 เก็บ "ส่วนเกินที่ b1 นับล่วงหน้าไป"
// เพราะ b1.pre(i) * i คิดเหมือนว่าของที่เพิ่มเริ่มตั้งแต่ช่องแรก ซึ่งเกินจริงไปเท่ากับ v*(l-1)
BIT b1(n), b2(n);

void addRange(int l, int r, long long v) {
    b1.add(l, v);
    if (r + 1 <= n) b1.add(r + 1, -v);
    b2.add(l, v * (l - 1));
    if (r + 1 <= n) b2.add(r + 1, -v * r);
}

long long pre(int i) { return b1.pre(i) * i - b2.pre(i); }
long long range(int l, int r) { return pre(r) - pre(l - 1); }

ท่าที่ 4 · หาตัวที่ k โดยไม่ต้องค้นซ้ำ

ท่าที่คนเขียนบ่อยที่สุดเวลาต้องหา "ตำแหน่งแรกที่ผลรวมสะสมถึง k" คือค้นทวิภาค แล้วเรียก pre ทุกครั้งที่เดา ซึ่งเป็น log²n แต่ต้นไม้เฟนวิกทำได้ในรอบเดียว เพราะตัวมันเองเก็บก้อนที่ยาวเป็นกำลังของสองอยู่แล้ว วิธีคือไล่บิตจากใหญ่ลงเล็ก แล้วก้าวเมื่อก้าวได้ เหลือ log n ก้าวเท่ากับการถามหนึ่งครั้ง

ท่านี้ใช้ได้เมื่อค่าในต้นไม้ไม่ติดลบ เพราะตอนนั้นผลรวมสะสมโตทางเดียว ถ้ามีค่าติดลบปนอยู่ ลำดับก็ไม่เรียงแล้ว การไล่บิตลงจะเดินผิดทางเงียบ ๆ โดยไม่มีอะไรฟ้อง โจทย์ที่ใช้ท่านี้เต็ม ๆ อยู่ในคลังนี้แล้ว คือ สายดีเอ็นเอตัวที่ k

// หาตำแหน่งแรกที่ผลรวมสะสมถึง k โดยไม่ต้องไล่ทีละช่อง
// ใช้ได้เมื่อค่าในต้นไม้ไม่ติดลบ เพราะตอนนั้นผลรวมสะสมเพิ่มขึ้นทางเดียว
// วิธีคือไล่บิตจากใหญ่ลงเล็ก แล้วก้าวเมื่อก้าวได้ ซึ่งอ่านตารางของต้นไม้ตรง ๆ
int kth(long long k) {
    int pos = 0;
    for (int pw = 1 << (31 - __builtin_clz(n)); pw > 0; pw >>= 1) {
        if (pos + pw <= n && t[pos + pw] < k) {
            pos += pw;
            k -= t[pos];        // ก้อนนี้กินไปแล้ว เหลือให้หาอีก k
        }
    }
    return pos + 1;             // ช่องถัดจากที่ก้าวมาไม่ถึง คือช่องที่ทำให้ถึง k
}

ท่าที่ 5 · หลายมิติ

ต้นไม้เฟนวิกซ้อนกันได้ตรง ๆ คือให้แต่ละช่องของต้นไม้แกนแรกเก็บต้นไม้อีกต้นของแกนที่สอง ทั้งการถามและการแก้กลายเป็นลูปสองชั้นที่กระโดดด้วยสูตรเดิมทั้งคู่ ราคาจึงเป็น log²n ต่อคำสั่ง และเป็น logᵈn ที่ d มิติ โค้ดยาวขึ้นราวสี่บรรทัด ท่านี้ทำงานอยู่ในข้อ คู่ที่ได้ยินกัน แล้ว จึงไม่ยกโค้ดมาซ้ำที่นี่

โจทย์ฝึก · ไล่จากง่ายไปยาก

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

ฝึกข้อ 1 ★☆☆☆☆ · ผลรวมของสี่เหลี่ยม

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

int main() {
    int R, C, q;
    scanf("%d %d %d", &R, &C, &q);

    // s[i][j] = ผลรวมของสี่เหลี่ยมตั้งแต่มุมซ้ายบน (1,1) ถึง (i,j)
    vector<vector<long long>> s(R + 1, vector<long long>(C + 1, 0));
    for (int i = 1; i <= R; i++)
        for (int j = 1; j <= C; j++) {
            long long v;
            scanf("%lld", &v);
            // แถวบนกับคอลัมน์ซ้ายทับกันตรงมุมซ้ายบน จึงต้องบวกคืนหนึ่งครั้ง
            s[i][j] = v + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }

    while (q--) {
        int r1, c1, r2, c2;
        scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
        printf("%lld\n", s[r2][c2] - s[r1 - 1][c2] - s[r2][c1 - 1] + s[r1 - 1][c1 - 1]);
    }
    return 0;
}

ฝึกข้อ 2 ★★☆☆☆ · นับคู่ที่สลับที่กันอยู่

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

int n;
vector<int> t;
void add(int i) { for (; i <= n; i += i & -i) t[i]++; }
int pre(int i) { int s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; }

int main() {
    scanf("%d", &n);
    vector<int> a(n);
    for (auto& x : a) scanf("%d", &x);

    // ค่าอาจใหญ่หรือติดลบ ย่อให้เป็นอันดับ 1..n ก่อน ต้นไม้จะได้มีขนาดเท่า n
    vector<int> v = a;
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    t.assign(n + 1, 0);
    long long ans = 0;
    for (int i = n - 1; i >= 0; i--) {          // เดินจากขวาไปซ้าย
        int r = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
        ans += pre(r - 1);                      // ของที่อยู่ขวาแล้วเล็กกว่า a[i]
        add(r);
    }
    printf("%lld\n", ans);
    return 0;
}

ฝึกข้อ 3 ★★★☆☆ · คู่ที่ค่าต่างกันไม่เกิน D

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

int main() {
    int n; long long D;
    scanf("%d %lld", &n, &D);
    vector<long long> a(n);
    for (auto& x : a) scanf("%lld", &x);

    sort(a.begin(), a.end());
    long long ans = 0;
    int l = 0;
    for (int r = 0; r < n; r++) {
        while (a[r] - a[l] > D) l++;   // ตัวชี้ซ้ายเดินหน้าอย่างเดียว ไม่เคยถอย
        ans += r - l;                  // ทุกตัวใน [l, r-1] จับคู่กับ r ได้
    }
    printf("%lld\n", ans);
    return 0;
}

ท่าที่สาม · แบ่งราก และเหตุผลที่เฟนวิกชนะมันอยู่ดี

สองท่าที่ผ่านมาห่างกันคนละโลก ผลรวมสะสมตอบเร็วแต่แก้ไม่ได้ เฟนวิกทำได้ทั้งสองอย่างแต่ต้องเข้าใจ เรื่องบิตก่อน ระหว่างสองอันนั้นมีท่าที่สามที่คิดออกได้เองโดยไม่ต้องรู้จักอะไรเลย และคุ้มพอที่จะผ่านโจทย์จำนวนมาก คือการแบ่งราก (sqrt decomposition)

แนวคิดมีบรรทัดเดียว คือหั่นอาเรย์เป็นก้อนละ √n ช่อง แล้วจดผลรวมของแต่ละก้อนไว้ ตอนแก้ค่าช่องหนึ่ง เราแก้ทั้งช่องนั้นและผลรวมของก้อนที่มันอยู่ ซึ่งเป็นงานคงที่ ตอนถามช่วง เราเดินทีละช่องเฉพาะเศษหัวกับเศษท้าย ส่วนกลางที่เป็นก้อนเต็ม เราอ่านจากผลรวมของก้อนตรง ๆ

ทำไมต้อง √n พอดี เพราะมีสองอย่างที่ดันกันอยู่ ถ้าก้อนใหญ่ เศษหัวเศษท้ายจะยาว ถ้าก้อนเล็ก จำนวนก้อนกลางจะมาก งานตอนถามคือ ขนาดก้อน บวก จำนวนก้อน ซึ่งน้อยที่สุดตอนสองค่านั้นเท่ากัน นั่นคือที่ √n ที่ n = 200,000 ขนาดก้อนจึงเป็น 447 และงานต่อคำถามเหลือราว 2√n คือ 894 ครั้ง

// แบ่งราก (sqrt decomposition): ผลรวมของช่วง กับแก้ทีละช่อง
// อินพุต: n q, อาเรย์ n ตัว, แล้ว q บรรทัด
//   1 i v  -> ตั้ง a[i] = v (i เริ่มจาก 0)
//   2 l r  -> ถามผลรวมช่อง l..r
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, q;
    if (scanf("%d %d", &n, &q) != 2) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);

    int B = max(1, (int)sqrt((double)n));       // ขนาดของก้อน
    int nb = (n + B - 1) / B;
    vector<long long> blk(nb, 0);
    for (int i = 0; i < n; i++) blk[i / B] += a[i];

    for (int t = 0; t < q; t++) {
        int op; scanf("%d", &op);
        if (op == 1) {
            int i; long long v; scanf("%d %lld", &i, &v);
            blk[i / B] += v - a[i];              // ก้อนที่ i อยู่ ขยับตามส่วนต่าง
            a[i] = v;
        } else {
            int l, r; scanf("%d %d", &l, &r);
            long long sum = 0;
            int bl = l / B, br = r / B;
            if (bl == br) {                      // อยู่ก้อนเดียวกัน เดินทีละช่อง
                for (int i = l; i <= r; i++) sum += a[i];
            } else {
                for (int i = l; i < (bl + 1) * B; i++) sum += a[i];        // เศษหัว
                for (int b = bl + 1; b < br; b++) sum += blk[b];           // ก้อนเต็มกลาง
                for (int i = br * B; i <= r; i++) sum += a[i];             // เศษท้าย
            }
            printf("%lld\n", sum);
        }
    }
    return 0;
}

// ตัวตรวจอิสระของแบ่งราก: เก็บอาเรย์เปล่า ถามก็บวกทีละช่อง
// ไม่มีก้อน ไม่มีรากที่สอง จึงไม่ได้ทดสอบแค่การพิมพ์
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, q;
    if (scanf("%d %d", &n, &q) != 2) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
    for (int t = 0; t < q; t++) {
        int op; scanf("%d", &op);
        if (op == 1) {
            int i; long long v; scanf("%d %lld", &i, &v);
            a[i] = v;
        } else {
            int l, r; scanf("%d %d", &l, &r);
            long long sum = 0;
            for (int i = l; i <= r; i++) sum += a[i];
            printf("%lld\n", sum);
        }
    }
    return 0;
}

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

สรุปบรรทัดเดียว

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

ข้อที่ใช้ของในบทนี้เต็ม ๆ คือ คู่ที่ได้ยินกัน ซึ่งเอาทั้งสามท่ามารวมกัน คือผลรวมสะสมสำหรับกระดานที่ไม่เปลี่ยน ต้นไม้เฟนวิกสำหรับตอนกวาดเส้น และการเรียงเพื่อทำให้เงื่อนไขสองแกนแยกกันได้