이 문제에서는 배열 arr[]과 Q개의 쿼리가 주어지며, 각 쿼리는 다음 두 가지 유형 중 하나입니다.
{1, L, R} − 범위 [L, R]에 속하는 배열 요소의 개수를 구합니다.
{2, index, val} − index 위치의 요소를 val 값으로 갱신합니다.
이 글에서는 C++를 사용하여 주어진 범위 내 값을 가진 배열 요소의 개수를 구하는 쿼리를 처리하는 프로그램을 작성하는 방법을 살펴보겠습니다.
문제 이해를 위한 예시
입력: arr[] = {1, 5, 2, 4, 2, 2, 3, 1, 3}
Q = 3
쿼리 = { {1, 4, 8}, {2, 6, 5}, {1, 1, 4} }
출력: 2 7
설명
쿼리 1: 범위 [4, 8]에 속하는 배열 요소의 개수를 셉니다. 해당하는 요소는 5와 4 두 개이므로 개수는 2입니다.
쿼리 2: arr[6]을 5로 갱신합니다. 갱신된 배열은 {1, 5, 2, 4, 2, 2, 5, 1, 3}입니다.
쿼리 3: 범위 [1, 4]에 속하는 배열 요소의 개수를 셉니다. 개수는 7입니다.
해결 접근 방식 1: 단순 순회
가장 간단한 해결 방법은 배열을 처음부터 끝까지 직접 순회하면서 L ≤ 요소 ≤ 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)입니다. 따라서 배열의 크기와 쿼리 수가 모두 많아지면 성능이 크게 저하될 수 있습니다.
해결 접근 방식 2: 펜윅 트리(Fenwick Tree)
더 효율적으로 문제를 해결하려면 바이너리 인덱스드 트리(Binary Indexed Tree), 즉 펜윅 트리 자료구조를 활용할 수 있습니다. 이 방식에서는 배열 요소의 '값'을 트리의 인덱스처럼 사용하여 각 값의 등장 횟수를 저장합니다. 그러면 자료구조에 기본 탑재된 합 계산 함수(calcSum)를 이용해 특정 범위에 속하는 요소의 개수를 손쉽게 구할 수 있습니다.
범위 [L, R]의 요소 개수는 다음과 같이 계산됩니다.
ElementCount[L, R] = calcSum(R) − calcSum(L − 1)
예시 코드
#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
펜윅 트리를 사용하면 개수 조회와 값 갱신 연산을 각각 O(log M)(M은 최댓값) 시간에 처리할 수 있으므로 전체 시간 복잡도는 O((N + Q) log M)이 됩니다. 다만 이 방식은 요소 값을 인덱스로 사용하기 때문에 값의 범위가 매우 크거나 음수가 포함된 경우에는 좌표 압축(coordinate compression)과 같은 전처리 과정이 필요할 수 있다는 점을 유의해야 합니다.