Sparsh 테이블은 범위 쿼리의 결과를 제공하는 데 사용되는 데이터 구조입니다. O(logN) 복잡성에서 대부분의 범위 쿼리 결과를 제공합니다. 최대 범위 쿼리의 경우 O(1)에서 결과를 계산할 수도 있습니다.
이 자습서에서는 배열이 제공되는 희소 테이블을 사용하는 범위 합계 쿼리의 문제에 대해 설명합니다. 예를 들어, 범위 L과 R에 있는 모든 요소의 합을 찾아야 합니다.
Input: arr[ ] = { 2, 4, 1, 5, 6, 3 }
query(1, 3),
query(0,2),
query(1, 5).
Output: 10
7
19
Input: arr[ ] = { 1, 2, 3, 4, 1, 4 }
query(0, 2),
query(2,4),
query(3, 5).
Output: 6
8
9 해결책을 찾기 위한 접근 방식
먼저 희소 테이블에서 답변을 검색하기 위해 희소 테이블을 만들어야 합니다. Sparse 테이블을 생성할 때 답변을 저장하기 위해 2차원 배열을 사용합니다. 희소 테이블에서 쿼리를 2의 거듭제곱으로 나눕니다. 희소 테이블을 만든 후 해당 테이블에서 쿼리를 검색하고 ( Left_index + 2^n - 1 <=Right_index 의 조건에서 변수에 값을 계속 추가합니다. ) 여기서 n은 2차원 배열의 열 크기입니다.
예시
위 접근 방식에 대한 C++ 코드
#include <bits/stdc++.h>
using namespace std;
// Maximum value of row of sparse table.
const int m = 1e5;
const int n = 16;
long long SPARSE[m][n + 1];
// query to be found with the help of a sparse table.
long long query(int l, int r){
long long sum = 0;
for (int i = n; i >= 0; i--) {
if (l + (1 << i) - 1 <= r) {
sum = sum + SPARSE[l][i];
l += 1 << i;
}
}
return sum;
}
int main(){
int arr[] = { 1, 2, 3, 4, 1, 4 };
int z = sizeof(arr) / sizeof(arr[0]);
// Building sparse table.
for (int i = 0; i < z; i++)
SPARSE[i][0] = arr[i];
for (int i = 1; i <= n; i++)
for (int j = 0; j <= z - (1 << j); j++)
SPARSE[j][i] = SPARSE[j][i - 1] + SPARSE[j + (1 << (i - 1))][i - 1];
cout <<"Sum: " << query(0, 2) << endl;
cout <<"Sum: " << query(2, 4) << endl;
cout <<"Sum: " << query(3, 5) << endl;
return 0;
} 출력
Sum: 6 Sum: 8 Sum: 4
결론
이 자습서에서는 다양한 쿼리에 매우 유용한 희소 테이블 생성에 대해 논의했습니다. 희소 테이블을 생성하고 해당 테이블에서 쿼리 결과를 가져옴으로써 이 문제를 해결하는 간단한 접근 방식에 대해 논의했습니다. 우리는 또한 C, Java, Python 등과 같은 프로그래밍 언어로 할 수 있는 이 문제에 대한 C++ 프로그램에 대해 논의했습니다. 이 튜토리얼이 도움이 되기를 바랍니다.