Binary Indexed Tree: Range Update และ Range Queries ใน C++

ในที่นี้ เรามีอาเรย์ขนาด n ที่มีค่าเริ่มต้นทั้งหมดเป็น 0 และมี query บางอย่างที่ต้องทำงานบนอาเรย์นี้ มี query 2 ประเภท:

• update(l, r, value) - บวก value ให้กับสมาชิกของอาเรย์ที่อยู่ระหว่างดัชนี l ถึง r ตัวอย่าง update(2, 4, 5) จะอัปเดตอาเรย์โดยวางค่า 5 ให้กับสมาชิกที่ดัชนี 2, 3, 4

• getRangeSum(l, r) - หาผลรวมของสมาชิกในช่วงจาก l ถึง r ตัวอย่าง getRangeSum(4, 7) จะหาผลรวมของสมาชิกที่ดัชนี 4, 5, 6, 7

ตัวอย่าง

อินพุต

n = 7, arr[7] = {0,0,0,0,0,0,0}
Q1 = update(3, 6, 4)
Q2 = update(0, 4, 2)
Q3 = Sum(2, 5)

เอาต์พุต

10

คำอธิบาย

Solving queries:
Q1 - update(3, 6, 4) = {0, 0, 0, 4, 4, 4, 4}
Q2 - update(0, 4, 2) = {2, 2, 2, 2, 2, 4, 4}
Q3 - sum(2, 5) = 2+2+2+4 = 10

วิธีแก้แบบ naive จะอัปเดตอาเรย์ทุกครั้งที่มี update query แล้วค่อยหาผลรวม แต่ไม่มีประสิทธิภาพ มาดูวิธีที่มีประสิทธิภาพมากกว่านี้

ลองดูผลของ update query ต่อ sum query Sum query เป็นรูปแบบ sum[l,r] เราจะแยกเป็น sum query รูปแบบ sum[0,k] แล้วลบผลรวมขอบล่างออกจากผลรวมขอบบน

sum[l,r] = sum[0,r] - sum[0,l-1]

ดังนั้น ผลของ sum[0,k] จะสะท้อนต่อ sum[l,r] ตัวแปร k จะอยู่ใน 3 ภูมิภาค ตามค่า relative และ range [l,r] ของ update query

ภูมิภาค 1 - k อยู่ระหว่าง 0 และ l คือ 0 < k < l

ในกรณีนี้ update query จะไม่ส่งผลต่อ sum query

ภูมิภาค 2 - k อยู่ระหว่าง l และ r คือ l ≤ k ≤ r

ในกรณีนี้ sum query จะนำค่าจาก l ถึง k ไปรวม

ภูมิภาค 3 - k มากกว่า r คือ k > r

ในกรณีนี้ sum query จะนำค่าทั้งหมดระหว่าง l ถึง r ไปรวม

โปรแกรมแก้ปัญหา Range Update และ Range Queries

// โปรแกรมแก้ปัญหา Range Update และ Range Queries

ตัวอย่าง

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

int getSum(int BITree[], int i) {
    int sum = 0;
    i++;
    while (i > 0) {
        sum += BITree[i];
        i -= i & (-i);
    }
    return sum;
}

void updateBITree(int BITree[], int n, int i, int val) {
    i = i + 1;
    while (i <= n) {
        BITree[i] += val;
        i += i & (-i);
    }
}

void update(int BITTree1[], int BITTree2[], int n, int l, int r, int value) {
    updateBITree(BITTree1, n, l, value);
    updateBITree(BITTree1, n, r + 1, -value);
    updateBITree(BITTree2, n, l, value * (l - 1));
    updateBITree(BITTree2, n, r + 1, -value * r);
}

int sum(int x, int BITTree1[], int BITTree2[]) {
    return (getSum(BITTree1, x) * x) - getSum(BITTree2, x);
}

int getRangeSum(int l, int r, int BITTree1[], int BITTree2[]) {
    return sum(r, BITTree1, BITTree2) - sum(l - 1, BITTree1, BITTree2);
}

int* createBITree(int n) {
    int* BITree = new int[n + 1];
    for (int i = 1; i <= n; i++)
        BITree[i] = 0;
    return BITree;
}

int main() {
    int n = 7;
    int *BITTree1, *BITTree2;
    BITTree1 = createBITree(n);
    BITTree2 = createBITree(n);
    update(BITTree1, BITTree2, n, 3, 6, 9);
    update(BITTree1, BITTree2, n, 0, 4, 5);
    cout << "The output of sum query after applying all update queries is \t"
         << getRangeSum(1, 5, BITTree1, BITTree2);
    return 0;
}

ผลลัพธ์

The output of sum query after applying all update queries is