주어진 배열과 여러 쿼리. 또한 쿼리에는 두 가지 유형이 있습니다. 즉, update[ L, R ]은 제곱근을 사용하여 요소를 L에서 R로 업데이트하는 것을 의미하고 쿼리[ L, R]은 L에서 R까지 요소의 합을 계산하는 것을 의미합니다. 예를 들어 1부터 시작하는 인덱스 배열을 가정합니다.
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 해결책을 찾기 위한 접근 방식
간단한 접근
쿼리가 끝날 때까지 루프를 사용하고 합계 쿼리에 대해 범위의 합계를 반환하고 업데이트 쿼리에 대해 배열을 업데이트할 수 있습니다. 그러나 이 프로그램의 시간 복잡도는 O(q * n)입니다. 효율적인 접근 방식을 찾아보겠습니다.
효율적인 접근
연산 횟수나 반복 횟수를 줄이면 프로그램이 효율적일 수 있습니다. 배열을 만들고 업데이트 및 합계 쿼리에 두 가지 함수를 사용하는 바이너리 인덱스 트리를 사용할 수 있습니다. 업데이트 쿼리의 경우 요소가 1이면 제곱근이 하나뿐이므로 업데이트할 필요가 없습니다. 이제 세트를 사용하여 1보다 큰 인덱스를 저장하고 이진 검색을 사용하여 L번째 인덱스를 찾고 모든 범위 요소가 업데이트될 때까지 증가시킬 수 있습니다. 그런 다음 업데이트된 값이 1이 되는지 확인한 다음 모든 업데이트 쿼리에 대해 항상 1이 되기 때문에 집합에서 해당 인덱스를 제거합니다.
합계 쿼리의 경우 쿼리(R) - 쿼리(L-1)를 수행할 수 있습니다.
예
위 접근 방식에 대한 C++ 코드
#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;
} 출력
query1: 14 query3: 10 query4: 7
결론
이 자습서에서는 배열에 대한 범위 합계 쿼리 및 범위 업데이트 쿼리에 대해 설명했습니다. 이 문제를 해결하기 위한 간단한 접근 방식과 Binary Indexed Tree를 사용하는 효율적인 접근 방식에 대해 논의했습니다. 우리는 또한 C, Java, Python 등과 같은 프로그래밍 언어로 할 수 있는 이 문제에 대한 C++ 프로그램에 대해 논의했습니다. 이 튜토리얼이 도움이 되기를 바랍니다.