큰 격자에 대한 사각형 쿼리의 요소 합계가

Question

큰 격자 10^5 * 10^5을 고려하십시오. n = 10^8 데이터 (x, y, v)에 대해 (x, y) 셀의 값이 v 인 것을 의미합니다. 다른 모든 셀에는 0이 포함됩니다. 약 q = 10^5에 대한 축 병렬 직사각형을 제공하는 쿼리가 요청됩니다. 출력은 그 직사각형 안의 셀에 포함 된 모든 값의 합이어야합니다. 이러한 쿼리를 처리하는 방법? 어떤 적합한 데이터 구조입니까?

데이터를 x 좌표로 정렬 할 수 있는데 평균적으로 좋을 것입니다. 하지만 최악의 경우는 O(nq)입니다. 어떤 도움이 필요합니까?

Answer 1

수정 쿼리가 없으므로 2D 바이너리 트리와 같은 복잡한 데이터 구조를 사용할 필요가 없습니다 (사실 2D 펜윅 트리가 존재하지만 간단하지만 메모리 소비가 너무 많음). 이 문제).

• 정렬 포인트 및 쿼리 x 좌표를 사용하여 ("이벤트"로 처리 된 사각형의 왼쪽과 오른쪽 모두) 모두 : 쿼리가 오프라인 인 경우

  는, 스윕 라인 알고리즘이있다.

• 동적 1D 범위 검색어 (예 : 펜윅 트리)에 사용되는 데이터 구조를 유지 관리합니다. 두 가지 기능이 있다고 가정 해 보겠습니다. add(y, value) 및 sum(y1, y2)
• 각 누적에 대해 일종의 "누적 카운터"도 저장하십시오 (A[i]). 왼쪽에서 오른쪽으로 모든 이벤트에 대해
• :
  • 는 점 (x, y, value)가 있다면 : add(y, value)를 호출합니다.
  • 길이가 (y_down, y_up, ...) 인 직사각형의 왼쪽 구석 인 경우 A[i] := sum(ydown, yup)입니다.
  • 오른쪽 구석 인 경우 : 주어진 검색어에 대한 답변은 sum(ydown, yup) - A[i]입니다.

시간 복잡도 : O((n + q)(log(q) + log(n))).
메모리 복잡도 : O(n + q).