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