ในที่นี้ เราได้รับอาร์เรย์ขนาด n ซึ่งในตอนแรกมีองค์ประกอบทั้งหมดเป็น 0 และมีการสืบค้นข้อมูลที่ต้องทำ แบบสอบถามมีสองประเภท -
-
อัพเดท(l,r,ค่า) − เพิ่มค่าให้กับองค์ประกอบของอาร์เรย์ที่อยู่ระหว่างดัชนี l ถึง r ตัวอย่างเช่น update(2, 4, 5) จะอัปเดตอาร์เรย์โดยวางองค์ประกอบ 2 ที่องค์ประกอบที่ดัชนี 4 และ 5
-
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 ในการแก้ปัญหานี้ แนวทางที่ไร้เดียงสาคือการอัปเดตอาร์เรย์ในการค้นหาการอัปเดตแต่ละครั้ง จากนั้นจึงหาผลรวมแต่วิธีนี้ไม่ได้ผล ดังนั้นเรามาเรียนรู้วิธีที่มีประสิทธิภาพมากขึ้นในการแก้ปัญหา
มาดูผลกระทบของการสืบค้นการปรับปรุงในแบบสอบถามผลรวม ผลรวมของแบบสอบถามเป็นรูปแบบ sum[l,r] เราจะแยกแบบสอบถามนี้ออกเป็นแบบสอบถามผลรวมของแบบฟอร์ม sum[0,k] แล้วลบผลรวมไปยังขีดจำกัดล่างจากผลรวมไปยังขีดจำกัดล่าง
sum[l,r] = sum[0,r] - sum[0,l]
ดังนั้น ผลกระทบของ sum[0,k] จะถูกสะท้อนบนผลรวม[l,r] ตัวแปรผลรวม k จะอยู่ใน 3 ส่วนที่แตกต่างกันตามค่าสัมพัทธ์ และจะอยู่ในช่วง [l,r] ของการสืบค้นข้อมูลอัปเดต
ภาค 1 − k อยู่ระหว่าง o และ l เช่น 0
ในกรณีนี้ แบบสอบถามการปรับปรุงจะไม่ส่งผลต่อการสอบถามผลรวม
ภาค 2 − k อยู่ระหว่าง l และ r เช่น l ≤ k ≤ r
ในกรณีนี้ แบบสอบถามผลรวมจะให้ค่าจาก l ถึง k
ภาค 3 − k มากกว่า r คือ k>r
ในกรณีนี้ เคียวรีผลรวมจะสร้างค่าทั้งหมดระหว่าง l ถึง r
มาดูโปรแกรมแก้ 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
