ในที่นี้ เราได้รับอาร์เรย์ขนาด 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