Trong bài toán này, chúng ta được cung cấp một dãy truy vấn arr [] và Q, mỗi truy vấn có thể là một trong hai loại,
-
{1, L, R} - Cho số phần tử mảng trong phạm vi [L, R].
-
{2, index, val} - Để cập nhật phần tử tại chỉ mục với val.
Nhiệm vụ của chúng tôi là tạo một chương trình để giải quyết các Truy vấn về số lượng các phần tử mảng có giá trị trong phạm vi đã cho trong C ++.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào :arr [] ={1, 5, 2, 4, 2, 2, 3, 1, 3}
Q =3
Truy vấn ={{1, 4, 8},
{2, 6, 5},
{1, 1, 4}}
Bỏ qua :3 7
Giải thích
Truy vấn 1:đếm các phần tử của mảng trong phạm vi [4, 8]. Đếm =1
Truy vấn 2:cập nhật phần tử arr [6] =5. Mảng mới, arr [] ={1, 5, 2, 4, 2, 2, 5, 1,3}
Truy vấn 1:đếm các phần tử của mảng trong phạm vi [4, 8]. Đếm =7
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là bằng cách duyệt trực tiếp mảng và tìm tất cả các phần tử nằm trong phạm vi tức là L =
Giải pháp để tiếp cận lặp lại một lần cho mỗi vòng lặp. Do đó, độ phức tạp về thời gian của nó là bậc O (Q * N).
Một cách tiếp cận tốt hơn để giải quyết vấn đề có thể là sử dụng cấu trúc dữ liệu Binary IndexedTree hoặc Fenwick Tree. Ở đây, chúng ta sẽ lưu trữ các phần tử của mảng trong cây, cho phép chúng ta sử dụng các phần tử của mảng làm chỉ mục. / P>
ElementCount [L, R] =getSum (R) - getSum (L - 1) Ví dụ
#include <iostream>
using namespace std;
int countElementInRange(int arr[], int N, int L, int R){
int ValueCount = 0;
for (int i = 0; i < N; i++) {
if (arr[i] >= L && arr[i] <= R) {
ValueCount++;
}
}
return ValueCount;
}
int main() {
int arr[] = {1, 5, 2, 4, 2, 2, 3, 1, 3};
int N = sizeof(arr) / sizeof(arr[0]);
int Q = 3;
int query[Q][3] = { {1, 4, 8},{2, 6, 5},{1, 1, 4}};
for(int i = 0; i < Q; i++){
if(query[i][0] == 1)
cout<<"The count of array elements with value in given range is " <<countElementInRange(arr,N, query[i][1], query[i][2])<<endl;
else if(query[i][0] == 2){
cout<<"Updating Value \n";
arr[query[i][1]] = query[i][2];
}
}
return 0;
} Đầu ra
The count of array elements with value in given range is 2
Updating Value
The count of array elements with value in given range is 7
Ví dụ
#include <iostream>
using namespace std;
class BinaryIndTree {
public:
int* BIT;
int N;
BinaryIndTree(int N) {
this->N = N;
BIT = new int[N];
for (int i = 0; i < N; i++) {
BIT[i] = 0;
}
}
void update(int index, int increment) {
while (index < N) {
BIT[index] += increment;
index += (index & -index);
}
}
int calcSum(int index) {
int sum = 0;
while (index > 0) {
sum += BIT[index];
index -= (index & -index);
}
return sum;
}
};
void UpdateValue(int* arr, int n, int index, int val, BinaryIndTree*fenwickTree){
int removedElement = arr[index];
fenwickTree->update(removedElement, -1);
arr[index] = val;
fenwickTree->update(val, 1);
}
int countElementInRange(int* arr, int n, int L, int R, BinaryIndTree*
fenwickTree) {
return fenwickTree->calcSum(R) - fenwickTree->calcSum(L - 1);
}
int main() {
int arr[] = { 1, 5, 2, 4, 2, 2, 3, 1, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
int Q = 3;
int query[Q][3] = { {1, 4, 8},{2, 6, 5},{1, 1, 4}};
int N = 100001;
BinaryIndTree* fenwickTree = new BinaryIndTree(N);
for (int i = 0; i < n; i++)
fenwickTree->update(arr[i], 1);
for(int i = 0; i < Q; i++){
if(query[i][0] == 1)
cout<<"The count of array elements with value in given range is "<<countElementInRange(arr, n, query[i][1], query[i][2],fenwickTree)<<endl;
else if(query[i][0] == 2){
cout<<"Updating Value \n";
UpdateValue(arr, n, query[i][1], query[i][2], fenwickTree);
}
}
return 0;
} Đầu ra
The count of array elements with value in given range is 2
Updating Value
The count of array elements with value in given range is 7