차례
문제 정책
"주어진 하위 배열에서 주어진 수보다 작거나 같은 요소 수"문제는 정수 배열과 q 개의 쿼리가 제공된다는 것을 나타냅니다. 두 가지 유형의 쿼리가 있습니다 à
- queryUpdate (i, v) : 배열 [i] = v를 업데이트하는 두 개의 정수 i와 v가 있습니다.
- queryPrint (left, right, k) : k보다 작은 범위 내의 정수 수를 인쇄합니다.
예
arr[]={2, 4, 6, 1, 5)
queryPrint(0, 2, 2)
queryUpdate(2, 8)
queryPrint(1, 3, 5)
queryUpdate(4, 3)
queryUpdate(1, 3)
queryPrint(1, 2, 4)
1 2 1
설명
queryPrint (0, 2, 2)는 인덱스 2에서 0, 즉 2까지 1보다 작거나 같은 요소 수를 인쇄합니다.
queryUpdate (2, 8)은 인덱스 2의 요소를 값 8로 업데이트합니다. 즉, arr은 {2, 4, 8, 1, 5}입니다.
queryPrint (1, 3, 5)는 인덱스 5에서 1, 즉 3까지 2보다 작거나 같은 요소 수를 인쇄합니다.
queryUpdate (4, 3)는 인덱스 4의 요소를 3으로 업데이트합니다. 즉, arr은 {2, 4, 8, 1, 3}입니다.
queryUpdate (1, 3)는 인덱스 1의 요소를 3으로 업데이트합니다. 즉, arr은 {2, 3, 8, 1, 3}입니다.
queryPrint (1, 2, 4)는 인덱스 4에서 1, 즉 2까지 1보다 작거나 같은 요소 수를 인쇄합니다.
하위 배열에서 주어진 값 <= 숫자를 찾는 알고리즘
- 나누기 정렬 n의 제곱근과 같은 크기의 블록으로, 여기서 n은 입력 배열의 크기입니다.
- 특정 블록의 배열에있는 최대 요소보다 하나 더 큰 이진 인덱스 트리를 만듭니다.
- 배열의 각 요소가 속한 블록을 찾아서 arr [i]에서 1로 블록의 BIT 배열을 업데이트합니다.
- 각 업데이트 쿼리에 대해. 인덱스에 대한 배열의 원래 값에있는 블록을 기준으로 BIT 배열의 값을 -1로 업데이트합니다.
- 특정 인덱스의 새 요소에서 값 1로 동일한 블록의 BIT 배열을 업데이트합니다.
- 각 인쇄 쿼리에 대해. k보다 작거나 같은 요소 값을 계산하기 위해 BIT 배열에 대한 쿼리를 작성하십시오. 전체 블록 또는 불완전 또는 부분 블록의 경우 모든 요소를 통과합니다.
설명
정수 배열과 두 가지 유형의 쿼리가 제공됩니다. 한 가지 쿼리는 주어진 특정 인덱스에서 값을 업데이트하는 것입니다. 그리고 또 다른 쿼리는 k보다 작은 요소의 수를 얻는 것입니다. 업데이트 쿼리의 경우 인덱스와 값이 제공됩니다. 값을 업데이트하겠습니다. v 배열 [i]의 주어진 인덱스에서. 인쇄 쿼리 또는 개수 쿼리의 경우 k보다 작거나 같은 정수의 수를 인쇄해야합니다.
배열을 몇 개의 블록으로 나눌 것입니다. 이 블록은 배열 길이의 제곱근 크기입니다. 모든 블록에 대해 우리는 이진 인덱스 트리. 이진 인덱스 트리의 크기는 배열 요소의 특정 블록에 대한 최대 요소보다 하나 더 커집니다. 각 블록에 대해 BIT 배열이 있으므로 배열 [i]의 각 위치에서 값 1로 값 비트 배열을 업데이트하고 배열의 각 요소에 대한 블록을 찾아 위와 동일한 절차를 따릅니다. arr [i]에서 해당 블록의 비트 배열을 1로 업데이트합니다.
각 업데이트 쿼리에 대해 BIT 배열을 업데이트하십시오. 각 배열 요소에 대한 블록이 있기 때문에. 특정 인덱스의 배열 값을 -1 값으로 업데이트하고 필요한 블록의 BIT 배열을 지정된 인덱스에있는 배열의 새 요소에서 값 1로 업데이트합니다. 인쇄 또는 값 계산 쿼리의 경우 루프를 통과하면됩니다. 전체 블록 또는 부분 전체 블록에 대한 두 가지 경우가 있습니다. 마침내 값을 반환합니다.
암호
숫자 <= 주어진 값을 찾기위한 C ++ 코드
#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string.h>
using namespace std;
const int MAX = 10001;
void update(int index, int block, int val, int bit[][MAX])
{
for (; index < MAX ; index += (index&-index))
bit[block][index] += val;
}
int queryPrint(int left, int right, int k, int arr[], int blockSize, int bit[][MAX])
{
int sum = 0;
while (left<right && left%blockSize!=0 && left!=0)
{
if (arr[left] <= k)
sum++;
left++;
}
while (left + blockSize <= right)
{
int index = k;
for (; index > 0 ; index -= index&-index)
sum += bit[left/blockSize][index];
left += blockSize;
}
while (left <= right)
{
if (arr[left] <= k)
sum++;
left++;
}
return sum;
}
void preprocess(int arr[], int blockSize, int n, int bit[][MAX])
{
for (int i=0; i<n; i++)
update(arr[i], i/blockSize, 1, bit);
}
void queryUpdate(int i, int v, int blockSize,int arr[], int bit[][MAX])
{
update(arr[i], i/blockSize, -1, bit);
update(v, i/blockSize, 1, bit);
arr[i] = v;
}
int main()
{
int arr[] = {2,4,6,1,5};
int n = sizeof(arr)/sizeof(arr[0]);
int blockSize = sqrt(n);
int bit[blockSize+1][MAX];
memset(bit, 0, sizeof(bit));
preprocess(arr, blockSize, n, bit);
cout << queryPrint (0, 2, 2, arr, blockSize, bit) << endl;
queryUpdate(2, 8, blockSize, arr, bit);
cout << queryPrint(1, 3, 5, arr, blockSize, bit) << endl;
queryUpdate(4, 3, blockSize, arr, bit);
queryUpdate(1, 3, blockSize, arr, bit);
cout << queryPrint (1, 2, 4, arr, blockSize, bit) << endl;
return 0;
}
1 2 1
숫자 <= 주어진 값을 찾기위한 Java 코드
class NumberElements
{
static final int MAX = 10001;
static void update(int index, int block, int val, int bit[][])
{
for ( ; index < MAX ; index += (index&-index))
bit[block][index] += val;
}
static int queryPrint(int left, int right, int k, int arr[], int blockSize, int bit[][])
{
int sum = 0;
while (left < right && left % blockSize != 0 && left != 0)
{
if (arr[left] <= k)
sum++;
left++;
}
while (left + blockSize <= right)
{
int index = k;
for (; index > 0 ; index -= index&-index)
sum += bit[left/blockSize][index];
left += blockSize;
}
while (left <= right)
{
if (arr[left] <= k)
sum++;
left++;
}
return sum;
}
static void buildArray(int arr[], int blockSize, int n, int bit[][])
{
for (int i=0; i<n; i++)
update(arr[i], i/blockSize, 1, bit);
}
static void queryUpdate(int i, int v, int blockSize, int arr[], int bit[][])
{
update(arr[i], i/blockSize, -1, bit);
update(v, i/blockSize, 1, bit);
arr[i] = v;
}
public static void main(String args[])
{
int arr[] = {2,4,6,1,5};
int blockSize = (int) Math.sqrt(arr.length);
int bit[][] = new int[blockSize+1][MAX];
buildArray(arr, blockSize, arr.length, bit);
System.out.println(queryPrint(0, 2, 2, arr, blockSize, bit));
queryUpdate(2, 8, blockSize, arr, bit);
System.out.println(queryPrint(1, 3, 5, arr, blockSize, bit));
queryUpdate(4, 3, blockSize, arr, bit);
queryUpdate(1, 3, blockSize, arr, bit);
System.out.println(queryPrint (1, 2, 4, arr, blockSize, bit));
}
}
1 2 1
복잡성 분석
시간 복잡성
O (1) 어레이 업데이트 및 O (N) 어레이 인쇄용.
공간 복잡성
O (N) 어디에 "엔" 배열의 요소 수입니다. “주어진 부분 배열에서 주어진 수보다 작거나 같은 요소의 수”문제는 선형 공간을 가지고 있습니다.
