Cho một mảng và một số truy vấn. Ngoài ra, có hai loại truy vấn, tức là cập nhật [L, R] có nghĩa là cập nhật các phần tử từ L đến R với căn bậc hai của chúng và truy vấn [L, R] có nghĩa là tính tổng các phần tử từ L đến R. Chúng tôi là giả sử một mảng được lập chỉ mục dựa trên 1, chẳng hạn
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 of 1st query is 1 means we need to calculate range sum from 1 to 3 i.e 9 + 4 + 1 = 14
1st element of 2nd query is 2 means we need to update range element from 1 to 2 with their square roots now new arr[] array is { 3, 2, 1, 5, 2, 3 }
1st element of 3rd query is 1 means we need to calculate range sum from 2 to 5 i.e 2 + 1 + 5 + 2 = 10
1st element of the 4th query is 1 means we need to calculate the range sum from 4 to 5 i.e 5 + 2 = 7
Input: nums[] = { 0, 3, 2, 4, 16, 2 }, Query[ ] = {{1, 1, 3}, {2, 2, 5}}
Output: 9 Phương pháp tiếp cận để tìm giải pháp
Phương pháp tiếp cận đơn giản
Chúng ta có thể sử dụng một vòng lặp cho đến khi các truy vấn kết thúc và trả về tổng của dải ô cho truy vấn sum và cập nhật mảng cho truy vấn cập nhật. Nhưng độ phức tạp về thời gian của chương trình này sẽ là O (q * n). Hãy tìm một cách tiếp cận hiệu quả.
Phương pháp tiếp cận hiệu quả
Chương trình có thể hiệu quả nếu chúng ta giảm số lượng hoạt động hoặc số lần lặp lại. Chúng ta có thể sử dụng Binary Indexed Trees, trong đó chúng ta tạo một mảng và sử dụng hai hàm để cập nhật và truy vấn tổng. Đối với truy vấn cập nhật, nếu phần tử là 1, thì không cần cập nhật phần tử đó vì căn bậc hai của nó sẽ là một duy nhất. Bây giờ chúng ta có thể sử dụng một tập hợp để lưu trữ chỉ số lớn hơn một và sử dụng tìm kiếm nhị phân để tìm chỉ số L và tăng nó cho đến khi mọi phần tử phạm vi được cập nhật. Sau đó, kiểm tra xem giá trị được cập nhật có trở thành một hay không, rồi xóa chỉ mục đó khỏi tập hợp vì nó sẽ luôn là 1 cho bất kỳ truy vấn cập nhật nào.
Đối với truy vấn tổng, chúng ta có thể thực hiện truy vấn (R) - truy vấn (L-1).
Ví dụ
Mã C ++ cho phương pháp tiếp cận trên
#include <bits/stdc++.h>
using namespace std;
// Maximum size input array can be
const int m = 200;
// Creating Binary Indexed tree.
int binary_indexed[m + 1];
// for update query
void update_q(int a, int x, int n){
while(a <= n) {
binary_indexed[a] += x;
a += a & -a;
}
}
// Function to calculate 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 for 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<int> s;
for (int i = 1; i < n; i++) {
// Inserting indexes in the set of elements that are greater than 1.
if (nums[i] > 1)
s.insert(i);
update_q(i, nums[i], n);
}
for (int i = 0; i < no_query; i++) {
// Checking 0th index for update query or sum query.
if (q[i][0] == 2) {
while (true) {
// Finding the left index using binary search
auto it = s.lower_bound(q[i][1]);
// checking whether it reaches right index.
if (it == s.end() || *it > q[i][2])
break;
q[i][1] = *it;
// updating array element to their square roots.
update_q(*it, (int)sqrt(nums[*it]) - nums[*it], n);
nums[*it] = (int)sqrt(nums[*it]);
//checking if updated value is 1 the removing it from 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;
} Đầu ra
query1: 14 query3: 10 query4: 7
Kết luận
Trong hướng dẫn này, chúng tôi đã thảo luận về truy vấn tổng phạm vi và truy vấn cập nhật phạm vi cho mảng. Chúng tôi đã thảo luận về một cách tiếp cận đơn giản để giải quyết vấn đề này và một cách tiếp cận hiệu quả bằng cách sử dụng Binary Indexed Tree. Chúng tôi cũng đã thảo luận về chương trình C ++ cho vấn đề này mà chúng tôi có thể làm với các ngôn ngữ lập trình như C, Java, Python, v.v. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.