30.2 Fenwick tree

หน้า 19.5 ทิ้งท้ายไว้ว่า prefix sum กับ difference array เร็วมากเมื่อข้อมูลไม่เปลี่ยน หรือเมื่อเปลี่ยนครบก่อนแล้วค่อยถาม แต่โจทย์ค่าย 2 และ TOI หลายข้อให้ข้อมูลเปลี่ยนสลับกับคำถามไปเรื่อยๆ เช่น ยอดขายของแต่ละสาขาที่เข้ามาทั้งวัน ระหว่างที่ผู้จัดการถามยอดรวมของหลายสาขา หน้านี้สอน Fenwick tree หรือ binary indexed tree (BIT) ที่ทั้งปรับค่าช่องเดียวและหาผลรวม prefix ได้ใน O(log N) โค้ดทั้งหมดสั้นกว่าสิบบรรทัด

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

โรงเรียนตั้งกล่องรับบริจาคไว้ 8 ห้องเรียน ยอดเงินในกล่องเปลี่ยนตลอดวัน และครูถามยอดรวมของห้องที่ l ถึง r เป็นระยะ ถ้าจำจากบทก่อนๆ จะมีสองทาง

เก็บแบบ	ปรับค่าช่องเดียว	ถามผลรวมช่วง
อาเรย์ธรรมดา ถามแล้ววนบวก	O(1)	O(N)
อาเรย์ prefix sum ปรับแล้วสร้างใหม่ตั้งแต่ช่องนั้นถึงท้าย	O(N)	O(1)

ทั้งสองทางมีงานหนึ่งที่เป็น O(N) ถ้ามี Q เหตุการณ์ปนกัน รวมเป็น O(NQ) ซึ่งเกินเวลาเมื่อ N กับ Q เป็นแสน Fenwick tree ยอมให้ทั้งสองงานเป็น O(log N) แทน

แบ่ง prefix ตามเลขฐานสอง

13 เขียนเป็นฐานสองได้ 1101 คือ 8 + 4 + 1 ผลรวม 13 ช่องแรกจึงแบ่งเป็นสามก้อนได้ คือช่อง 1 ถึง 8 ช่อง 9 ถึง 12 และช่อง 13 แต่ละก้อนยาวเป็นกำลังของสอง ถ้าเตรียมผลรวมของก้อนพวกนี้ไว้ล่วงหน้า หาผลรวม 13 ช่องแรกก็บวกแค่สามค่า

Fenwick tree เตรียมไว้ในอาเรย์ tree ขนาด N + 1 โดยใช้กฎข้อเดียว tree[i] เก็บผลรวมของก้อนที่จบที่ช่อง i และยาวเท่ากับ bit ขวาสุดของ i เช่น 12 คือ 1100 bit ขวาสุดมีค่า 4 tree[12] จึงเก็บช่อง 9 ถึง 12 ส่วน 13 คือ 1101 bit ขวาสุดมีค่า 1 tree[13] เก็บแค่ช่อง 13 ภาพนี้วาดก้อนของ tree[1] ถึง tree[16] ก้อนที่ยาวช่องเดียวเขียนไว้แค่เลขช่อง

ก้อนที่ระบายสีคือสามก้อนที่ต่อกันเป็น 13 ช่องแรกพอดี สังเกตว่าเลขคี่ทุกตัวมีก้อนยาวหนึ่งช่อง และ tree[16] เก็บผลรวมทั้ง 16 ช่อง prefix ใดๆ แบ่งเป็นก้อนได้ไม่เกินจำนวน bit ที่เป็น 1 ของมัน ซึ่งไม่เกิน log₂ N + 1 ก้อน

หา bit ขวาสุดด้วย i & -i

ค่าของ bit ขวาสุดที่เป็น 1 เรียกกันว่า lowbit หาได้ด้วย i & -i ใช้ & จากหน้า 12.3 เหตุผลอยู่ที่วิธีเก็บเลขติดลบ คอมพิวเตอร์เก็บ -i ด้วยการกลับทุก bit ของ i แล้วบวก 1 เรียกว่า two's complement โปรแกรมนี้พิมพ์ 8 bit ขวาของแต่ละค่าออกมาดู

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

string last_bits(int x)
{
    string bits = "";
    for (int k = 7; k >= 0; k--) {
        bits += ((x >> k) & 1) ? '1' : '0';
    }
    return bits;
}

int main()
{
    int numbers[] = {12, 13, 6, 8};
    for (int i : numbers) {
        cout << "i = " << setw(2) << i << "  i: " << last_bits(i) << "  -i: " << last_bits(-i)
             << "  i & -i: " << last_bits(i & -i) << " = " << (i & -i) << '\n';
    }
    return 0;
}

i = 12  i: 00001100  -i: 11110100  i & -i: 00000100 = 4
i = 13  i: 00001101  -i: 11110011  i & -i: 00000001 = 1
i =  6  i: 00000110  -i: 11111010  i & -i: 00000010 = 2
i =  8  i: 00001000  -i: 11111000  i & -i: 00001000 = 8

ดู 12 ที่เป็น 00001100 กลับทุก bit ได้ 11110011 บวก 1 แล้ว 1 ที่ท้ายทดต่อไปเรื่อยๆ จนไปหยุดตรงหลักที่เคยเป็น bit 1 ขวาสุดของ 12 ได้ 11110100 หลักทางขวาของจุดนั้นกลับเป็น 0 เหมือนเดิม หลักนั้นเองกลับเป็น 1 ส่วนหลักทางซ้ายทั้งหมดยังเป็นค่าที่กลับแล้ว ซึ่งตรงข้ามกับของ 12 พอ & กัน จึงเหลือแค่ bit นั้น bit เดียว ได้ 4

ถามผลรวมและปรับค่า

ถามผลรวม i ช่องแรก บวก tree[i] ซึ่งครอบช่วงท้ายยาว lowbit ของ i แล้วตัดช่วงนั้นทิ้งด้วย i -= i & -i ทำซ้ำจน i เป็น 0 ทุกรอบ bit 1 ขวาสุดหายไปหนึ่งตัว เช่น 13 → 12 → 8 → 0

ปรับค่าช่อง i ทุกก้อนที่ครอบช่อง i ต้องเปลี่ยนตาม ในภาพ ก้อนที่ครอบคอลัมน์ 5 คือ tree[5] tree[6] tree[8] และ tree[16] ไล่ได้ด้วย i += i & -i ซึ่งกระโดดไปก้อนถัดไปที่ใหญ่กว่าและยังครอบช่อง i อยู่ จน i เกิน N

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

int main()
{
    int n = 16;
    int i = 13;
    cout << "sum of first 13 uses:";
    while (i > 0) {
        cout << " tree[" << i << "]";
        i -= i & -i;
    }
    cout << '\n';
    i = 5;
    cout << "changing a[5] updates:";
    while (i <= n) {
        cout << " tree[" << i << "]";
        i += i & -i;
    }
    cout << '\n';
    return 0;
}

sum of first 13 uses: tree[13] tree[12] tree[8]
changing a[5] updates: tree[5] tree[6] tree[8] tree[16]

ทั้งสองลูปวนไม่เกินจำนวนหลักของ N ในฐานสอง N เป็นแสนวนไม่เกิน 17 รอบ ทั้งถามและปรับค่าจึงเป็น O(log N) ผลรวมช่วง l ถึง r ได้จาก prefix_sum(r) - prefix_sum(l - 1) แบบเดียวกับ prefix sum ในหน้า 5.4

โปรแกรมเต็ม

เหตุการณ์แบบ 1 i v คือกล่องห้อง i ได้เงินเพิ่ม v บาท ถ้า v ติดลบคือครูนำเงินออกไป เหตุการณ์แบบ 2 l r คือถามยอดรวมห้อง l ถึง r

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

int n;
vector<long long> tree; // (1)!

void add(int i, long long delta)
{
    for (; i <= n; i += i & -i) {
        tree[i] += delta;
    }
}

long long prefix_sum(int i)
{
    long long total = 0;
    for (; i > 0; i -= i & -i) {
        total += tree[i];
    }
    return total;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    tree.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long value;
        cin >> value;
        add(i, value); // (2)!
    }
    for (int k = 0; k < q; k++) {
        int type, a, b;
        cin >> type >> a >> b;
        if (type == 1) {
            add(a, b);
        } else {
            cout << "sum " << a << ".." << b << " = " << prefix_sum(b) - prefix_sum(a - 1) << '\n'; // (3)!
        }
    }
    return 0;
}

ใช้ช่อง 1 ถึง n ช่อง 0 ไม่ใช้ เพราะ 0 ไม่มี bit ที่เป็น 1 เลย เหตุผลอยู่ในส่วนลองทำให้พัง
เริ่มจากต้นไม้ที่เป็น 0 ทั้งหมด แล้วบวกค่าเริ่มต้นเข้าไปทีละช่อง ใช้ O(N log N) ซึ่งเร็วพอสำหรับ N เป็นแสน
ผลรวม b ช่องแรกลบผลรวม a - 1 ช่องแรก

8 6
30 0 15 20 0 45 10 5
2 1 8
2 3 6
1 5 25
1 3 -15
2 3 6
2 5 5

sum 1..8 = 125
sum 3..6 = 80
sum 3..6 = 90
sum 5..5 = 25

คำถามที่สองได้ 15 + 20 + 0 + 45 = 80 จากนั้นห้อง 5 ได้เงินเพิ่ม 25 และครูนำเงินห้อง 3 ออก 15 คำถามเดิมจึงได้ 0 + 20 + 25 + 45 = 90 ผลรวมช่วงใหญ่ได้ถึง N × 10⁹ ต้นไม้จึงเก็บ long long

บวกทั้งช่วง ถามทีละช่อง

กลับด้านได้ด้วยความคิดของ difference array ในหน้า 19.5 การบวก g ให้ช่อง l ถึง r เปลี่ยนแค่สองจุด คือบวก g ที่ l และลบ g ที่ r + 1 ค่าจริงของช่อง i คือผลรวมของการเปลี่ยนแปลงตั้งแต่ช่อง 1 ถึง i ถ้าเก็บการเปลี่ยนแปลงไว้ใน Fenwick tree แทนอาเรย์ธรรมดา ค่าของช่อง i ก็คือ prefix_sum(i) ถามสลับกับบวกได้ตลอด ตัวอย่างนี้คือไฟประดับ 6 ดวงในงานโรงเรียน เหตุการณ์ 1 l r g เพิ่มความสว่างดวง l ถึง r อีก g หน่วย และ 2 i ถามความสว่างของดวง i

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

int n;
vector<long long> tree;

void add(int i, long long delta)
{
    for (; i <= n; i += i & -i) {
        tree[i] += delta;
    }
}

long long prefix_sum(int i)
{
    long long total = 0;
    for (; i > 0; i -= i & -i) {
        total += tree[i];
    }
    return total;
}

int main()
{
    int q;
    cin >> n >> q;
    tree.assign(n + 1, 0);
    for (int k = 0; k < q; k++) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r;
            long long amount;
            cin >> l >> r >> amount;
            add(l, amount);
            add(r + 1, -amount); // (1)!
        } else {
            int i;
            cin >> i;
            cout << "lamp " << i << " = " << prefix_sum(i) << '\n';
        }
    }
    return 0;
}

ถ้า r เป็นดวงสุดท้าย r + 1 เกิน n ลูปใน add ไม่ทำงานเลย ซึ่งถูกต้อง เพราะไม่มีดวงไหนอยู่หลังดวงสุดท้ายให้ลบ

lamp 3 = 10
lamp 4 = 13
lamp 6 = 3
lamp 1 = 0

ถ้าโจทย์ต้องการทั้งบวกทั้งช่วงและถามผลรวมทั้งช่วง ยังใช้ Fenwick tree ได้ด้วยการเก็บสองต้น แต่เกินขอบเขตของหน้านี้ โจทย์แบบนั้นใช้ segment tree แบบ lazy propagation ที่จะพูดถึงในหน้า 30.3 ได้เหมือนกัน

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

วัดบนเครื่องเดียวกับหน้า 18.2 แบบ -O2 ข้อมูล N ช่องเป็นเลขสุ่มไม่เกิน 10⁹ มี Q = N เหตุการณ์ ครึ่งหนึ่งปรับค่าช่องสุ่ม อีกครึ่งถามผลรวมช่วงสุ่ม รันแต่ละแบบ 5 รอบ ตารางเป็นค่ากลาง

วิธี	N = Q = 100000	N = Q = 200000
อาเรย์ธรรมดา ถามแล้ววนบวก O(NQ)	0.88 วินาที (5 รอบอยู่ระหว่าง 0.44 ถึง 1.09)	1.61 วินาที
prefix sum สร้างใหม่ทุกครั้งที่ปรับ O(NQ)	0.71 วินาที	2.51 วินาที
Fenwick tree O((N + Q) log N)	0.050 วินาที	0.077 วินาที

สองวิธีแรกยังพอไหวที่แสน เพราะ -O2 บวกเลขที่เรียงติดกันในหน่วยความจำได้เร็วมาก แต่พอข้อมูลเพิ่มเป็นสองเท่า งานเพิ่มเป็นราวสี่เท่า วิธีสร้าง prefix sum ใหม่ช้าลงจาก 0.71 เป็น 2.51 วินาที ส่วน Fenwick tree ใช้เวลาเกือบทั้งหมดไปกับการอ่านข้อมูล

ลองทำให้พัง

แบบที่ 1 เก็บตั้งแต่ช่อง 0

ติดนิสัยใช้อาเรย์ตั้งแต่ช่อง 0 จึงเรียก add ด้วย i ตั้งแต่ 0

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

int n;
vector<long long> tree;

void add(int i, long long delta)
{
    for (; i <= n; i += i & -i) {
        tree[i] += delta;
    }
}

int main()
{
    n = 5;
    tree.assign(n + 1, 0);
    int values[] = {4, 7, 1, 3, 9};
    for (int i = 0; i < n; i++) {
        add(i, values[i]);
    }
    cout << "built\n";
    return 0;
}

โปรแกรมค้าง ไม่พิมพ์ built ออกมาเลย ทดลองรันไว้ 5 วินาทีแล้วต้องสั่งหยุดเอง เพราะ 0 & -0 ได้ 0 บรรทัด i += i & -i จึงไม่ทำให้ i ขยับ tree[0] ถูกบวกไปเรื่อยๆ ไม่มีวันจบ ถ้าส่งให้ grader จะได้ผลว่าเกินเวลา ถ้าข้อมูลในโจทย์นับจาก 0 ให้บวกหนึ่งก่อนเรียก add และ prefix_sum ทุกครั้ง

แบบที่ 2 โจทย์ให้แทนค่า แต่บวกค่า

นักเรียน 4 คนได้คะแนน 80 65 90 70 ครูตรวจกระดาษคำตอบของคนที่ 2 ใหม่ แล้วแก้คะแนนเป็น 75 ผลรวมที่ถูกต้องคือ 80 + 75 + 90 + 70 = 315 โปรแกรมนี้ใช้ Fenwick tree เหมือนเดิม แต่ส่งคะแนนใหม่ให้ add ตรงๆ

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

int n;
vector<long long> tree;

void add(int i, long long delta)
{
    for (; i <= n; i += i & -i) {
        tree[i] += delta;
    }
}

long long prefix_sum(int i)
{
    long long total = 0;
    for (; i > 0; i -= i & -i) {
        total += tree[i];
    }
    return total;
}

int main()
{
    int q;
    cin >> n >> q;
    tree.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long value;
        cin >> value;
        add(i, value);
    }
    for (int k = 0; k < q; k++) {
        int type, a, b;
        cin >> type >> a >> b;
        if (type == 1) {
            add(a, b);
        } else {
            cout << prefix_sum(b) - prefix_sum(a - 1) << '\n';
        }
    }
    return 0;
}

4 3
80 65 90 70
2 1 4
1 2 75
2 1 4

305
380

ได้ 380 เพราะ 65 เดิมยังอยู่ในต้นไม้ แล้วบวก 75 ทับลงไปอีก Fenwick tree รู้จักแต่การบวก ไม่รู้ว่าค่าเดิมของช่องคือเท่าไร ถ้าโจทย์บอกค่าใหม่ ต้องเก็บค่าปัจจุบันของทุกช่องไว้อีกอาเรย์ แล้วบวกส่วนต่าง

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

int n;
vector<long long> tree;

void add(int i, long long delta)
{
    for (; i <= n; i += i & -i) {
        tree[i] += delta;
    }
}

long long prefix_sum(int i)
{
    long long total = 0;
    for (; i > 0; i -= i & -i) {
        total += tree[i];
    }
    return total;
}

int main()
{
    int q;
    cin >> n >> q;
    tree.assign(n + 1, 0);
    vector<long long> score(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> score[i];
        add(i, score[i]);
    }
    for (int k = 0; k < q; k++) {
        int type, a, b;
        cin >> type >> a >> b;
        if (type == 1) {
            add(a, b - score[a]); // (1)!
            score[a] = b;
        } else {
            cout << prefix_sum(b) - prefix_sum(a - 1) << '\n';
        }
    }
    return 0;
}

ส่วนต่างระหว่างค่าใหม่กับค่าเดิม ค่าใหม่น้อยกว่าเดิมก็ได้ส่วนต่างติดลบ ซึ่ง add รับได้ แล้วต้องจำค่าใหม่ไว้ใช้รอบหน้าด้วย

4 3
80 65 90 70
2 1 4
1 2 75
2 1 4

305
315

สรุป

tree[i] เก็บผลรวมของก้อนยาว i & -i ที่จบที่ช่อง i ใช้ช่อง 1 ถึง N เท่านั้น
ผลรวม i ช่องแรก วน i -= i & -i ปรับค่าช่อง i วน i += i & -i ทั้งคู่เป็น O(log N)
ผลรวมช่วงคือ prefix_sum(r) - prefix_sum(l - 1)
เก็บการเปลี่ยนแปลงแบบ difference array ไว้ในต้นไม้ ได้การบวกทั้งช่วงกับการถามค่าทีละช่องใน O(log N)
Fenwick tree บวกได้อย่างเดียว ถ้าโจทย์ให้แทนค่า ต้องบวกส่วนต่างจากค่าเดิม
ใช้กับค่าน้อยสุดหรือมากสุดทั่วไปไม่ได้ เพราะลบก้อนที่เกินออกไม่ได้ งานแบบนั้นใช้ segment tree ในหน้าถัดไป