กำหนดอาร์เรย์และคิวรีหลายคิวรี นอกจากนี้ยังมีสองประเภทของคิวรี คือ update[L, R] หมายถึงอัปเดตองค์ประกอบจาก L ถึง R ด้วย square root ของพวกมัน และ query[L, R] หมายถึงคำนวณผลรวมขององค์ประกอบจาก L ถึง R เราสมมติอาร์เรย์ที่ใช้ 1-based indexing ตัวอย่างเช่น:
Input: nums[] = { 0, 9, 4, 1, 5, 2, 3 }
Query[] = { {1, 1, 3}, {2, 1, 2}, {1, 2, 5}, {1, 4, 5} }
Output: 14 10 7
1st element ของ 1st query คือ 1 หมายถึงเราต้องคำนวณ range sum จาก 1 ถึง 3 คือ 9 + 4 + 1 = 14
1st element ของ 2nd query คือ 2 หมายถึงเราต้องอัปเดต range element จาก 1 ถึง 2 ด้วย square root ตอนนี้ arr[] ใหม่คือ { 3, 2, 1, 5, 2, 3 }
1st element ของ 3rd query คือ 1 หมายถึงเราต้องคำนวณ range sum จาก 2 ถึง 5 คือ 2 + 1 + 5 + 2 = 10
1st element ของ 4th query คือ 1 หมายถึงเราต้องคำนวณ range sum จาก 4 ถึง 5 คือ 5 + 2 = 7
Input: nums[] = { 0, 3, 2, 4, 16, 2 }
Query[] = {{1, 1, 3}, {2, 2, 5}}
Output: 9
วิธีการหาคำตอบ
วิธีง่าย (Simple Approach)
เราสามารถใช้ลูปจนกว่าคิวรีจะจบและคืนค่าผลรวมของช่วงสำหรับ sum query และอัปเดตอาร์เรย์สำหรับ update query แต่ความซับซ้อนด้านเวลาของโปรแกรมนี้จะเป็น O(q × n) มาดูวิธีที่มีประสิทธิภาพ
วิธีที่มีประสิทธิภาพ (Efficient Approach)
โปรแกรมสามารถมีประสิทธิภาพได้ถ้าเราลดจำนวนการดำเนินการหรือจำนวนการวนซ้ำ เราสามารถใช้ Binary Indexed Trees (Fenwick Tree) ซึ่งเราสร้างอาร์เรย์และใช้สองฟังก์ชันสำหรับ update และ sum query สำหรับ update query ถ้าองค์ประกอบเป็น 1 ไม่มีความจำเป็นต้องอัปเดตเพราะ square root จะเป็น 1 เสมอ ตอนนี้เราสามารถใช้ set เพื่อเก็บดัชนีของค่าที่มากกว่า 1 และใช้ binary search สำหรับหา Lth index และเพิ่มมันจนกว่าองค์ประกอบทุกตัวในช่วงจะถูกอัปเดต จากนั้นตรวจสอบว่าค่าที่อัปเดตกลายเป็น 1 แล้ว ลบดัชนีนั้นออกจาก set เพราะมันจะเป็น 1 เสมอสำหรับ update queries ใดๆ
สำหรับ sum query เราสามารถทำ query(R) - query(L-1) ได้
ตัวอย่าง
โค้ด C++ สำหรับวิธีข้างต้น
#include <bits/stdc++.h>
using namespace std;
// ขนาดสูงสุดของ input array
const int m = 200;
// สร้าง Binary Indexed Tree
int binary_indexed[m + 1];
// ฟังก์ชันสำหรับ update query
void update_q(int a, int x, int n){
while(a <= n) {
binary_indexed[a] += x;
a += a & -a;
}
}
// ฟังก์ชันคำนวณ sum range
int sum_q(int a){
int s = 0;
while(a > 0) {
s += binary_indexed[a];
a -= a & -a;
}
return s;
}
int main(){
int no_query = 4;
int nums[] = { 0, 9, 4, 1, 5, 2, 3 };
int n = sizeof(nums) / sizeof(nums[0]);
// 2-D array สำหรับ queries
int q[no_query + 1][3];
q[0][0] = 1, q[0][1] = 1, q[0][2] = 3;
q[1][0] = 2, q[1][1] = 1, q[1][2] = 2;
q[2][0] = 1, q[2][1] = 2, q[2][2] = 5;
q[3][0] = 1, q[3][1] = 4, q[3][2] = 5;
set s;
for (int i = 1; i < n; i++) {
// แทรกดัชนีใน set ขององค์ประกอบที่มากกว่า 1
if (nums[i] > 1)
s.insert(i);
update_q(i, nums[i], n);
}
for (int i = 0; i < no_query; i++) {
// ตรวจสอบ index 0 สำหรับ update query หรือ sum query
if (q[i][0] == 2) {
while (true) {
// หา left index โดยใช้ binary search
auto it = s.lower_bound(q[i][1]);
// ตรวจสอบว่ามันถึง right index แล้ว
if (it == s.end() || *it > q[i][2])
break;
q[i][1] = *it;
// อัปเดตองค์ประกอบอาร์เรย์เป็น square root
update_q(*it, (int)sqrt(nums[*it]) - nums[*it], n);
nums[*it] = (int)sqrt(nums[*it]);
// ตรวจสอบถ้าค่าที่อัปเดตเป็น 1 แล้วลบออกจาก set
if (nums[*it] == 1)
s.erase(*it);
q[i][1]++;
}
} else {
cout << "query" << i+1 << ": " << (sum_q(q[i][2]) - sum_q(q[i][1] - 1)) << endl;
}
}
return 0;
} ผลลัพธ์
query1: 14 query3: 10 query4: 7
สรุป
ในบทช่วยสอนนี้ เราอภิปราย range sum query และ range update query สำหรับอาร์เรย์ เราอภิปรายวิธีง่ายๆ ในการแก้ปัญหานี้และวิธีที่มีประสิทธิภาพโดยใช้ Binary Indexed Tree เรายังอภิปรายโปรแกรม C++ สำหรับปัญหานี้ซึ่งเราสามารถทำได้กับภาษาโปรแกรมมิ่งอย่าง C, Java, Python ฯลฯ เราหวังว่าบทช่วยสอนนี้จะเป็นประโยชน์
