ในปัญหานี้ เราได้รับอาร์เรย์ arr[] และคิวรีคิว ซึ่งแต่ละอันสามารถเป็นหนึ่งในสองประเภท
-
{1, L, R}− สำหรับการนับองค์ประกอบอาร์เรย์ในช่วง [L, R]
-
{2, index, val}− สำหรับอัปเดตองค์ประกอบที่ดัชนีด้วย val.
งานของเราคือการสร้างโปรแกรมเพื่อแก้ปัญหาการสืบค้นสำหรับการนับองค์ประกอบอาร์เรย์ที่มีค่าในช่วงที่กำหนดใน C ++
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล :arr[] ={1, 5, 2, 4, 2, 2, 3, 1, 3}
Q =3
ข้อความค้นหา ={ {1, 4, 8},
{2, 6, 5},
{1, 1, 4}}
เอาท์พุต :3 7
คำอธิบาย
แบบสอบถาม 1:นับองค์ประกอบอาร์เรย์ในช่วง [4, 8] นับ =1
แบบสอบถาม 2:อัปเดตองค์ประกอบ arr[6] =5. อาร์เรย์ใหม่ arr[] ={1, 5, 2, 4, 2, 2, 5, 1,3}
แบบสอบถาม 1:นับองค์ประกอบอาร์เรย์ในช่วง [4, 8] นับ =7
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาง่ายๆ ก็คือการข้ามผ่านอาร์เรย์โดยตรงและค้นหาองค์ประกอบที่อยู่ในช่วง เช่น L =<องค์ประกอบ =
วิธีแก้ปัญหาในการวนซ้ำทุกๆ รอบ ดังนั้นความซับซ้อนของเวลาจึงอยู่ในลำดับ O(Q*N)
แนวทางที่ดีกว่าในการแก้ปัญหาคือการใช้โครงสร้างข้อมูล Binary IndexedTree หรือ Fenwick Tree ที่นี่ เราจะเก็บองค์ประกอบของ thearray ไว้ในทรี ซึ่งจะทำให้เราใช้องค์ประกอบอาร์เรย์เป็นดัชนี และเราสามารถค้นหาจำนวนองค์ประกอบของช่วงได้อย่างง่ายดายโดยใช้ getSumfunction ซึ่งสร้างขึ้นสำหรับโครงสร้างข้อมูล
ElementCount[L, R] =getSum(R) - getSum(L - 1)ตัวอย่าง
#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;
} ผลลัพธ์
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
ตัวอย่าง
#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;
} ผลลัพธ์
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
