우리가 좋아하는 구간 합 문제를 다시 생각해 봅시다. 다만 이번에는 모든 인덱스가 $10^5$이나 $10^6$ 범위가 아니라 $10^9$, 심지어 $10^{18}$까지입니다.
모든 점근적 복잡도는 여전히 대체로 만족스럽습니다:
$$ \log_2 10^6 \approx 20 \\ \log_2 10^9 \approx 30 \\ \log_2 10^{18} \approx 60 $$유일한 문제는 $n$에 선형인 시간과 메모리가 드는 구축 단계입니다.
이 문제는 처음부터 트리의 모든 정점을 명시적으로 생성하지 않는 방식으로 해결할 수 있습니다. 처음에는 루트만 생성하고, 나머지 정점은 기본값이 아닌 무언가를 기록해야 할 때 그때그때 생성하겠습니다. lazy propagation에서와 같습니다:
struct Segtree {
int lb, rb;
int s = 0;
Segtree *l = 0, *r = 0;
Segtree(int lb, int rb) : lb(lb), rb(rb) {
// а тут ничего нет
}
// создает детей, если нужно
void extend() {
if (!l && lb + 1 < rb) {
int t = (lb + rb) / 2;
l = new segtree(lb, t);
r = new segtree(t, rb);
}
}
// ...
};
이제 push와 마찬가지로, 모든 메서드의 시작 부분에서 자식 노드가 생성되어 있는지 확인하고, 생성되어 있지 않다면 생성하겠습니다.
void add(int k, int x) {
extend();
s += x;
if (l) {
if (k < l->rb)
l->add(k, x);
else
r->add(k, x);
}
}
int sum(int lq, int rq) {
if (lb >= lq && rb <= rq)
return s;
if (max(lb, lq) >= min(rb, rq))
return 0;
extend();
return l->sum(lq, rq) + r->sum(lq, rq);
}
이러한 방법은 주로 포인터 기반 구현에만 적용할 수 있지만, 인덱스를 사용하는 경우에는 정점을 배열이 아닌 해시 테이블에 저장할 수 있습니다. 이렇게 하면 쿼리 처리 시간은 늘어나지만 점근적으로 늘어나지는 않습니다. 또한 어느 경우든 각 쿼리마다 새 정점을 만들기 위해 $O(\log n)$의 추가 메모리가 필요하며, 이로 인해 메모리 사용량은 보통 $O(q \log n)$이 된다는 점에 유의하십시오.
또한 모든 쿼리를 미리 알고 있다면, 쿼리를 처리하기 전에 그 좌표를 간단히 압축할 수 있습니다. 저자는 보통 다음과 같이 합니다:
vector<int> compress(vector<int> a) {
vector<int> b = a;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
for (int &x : a)
x = int(lower_bound(b.begin(), b.end(), x) - b.begin());
return a;
}
대부분의 경우 동적 구축을 사용하는 것은 빈대 잡으려다 초가삼간 태우는 격입니다. 먼저 더 간단한 방법을 시도해 보십시오. 어쩌면 모든 것이 그냥 set에 들어갈 수도 있습니다.