Sqrt 트리¶
원소 $n$개를 담은 배열 $a$와 결합 법칙을 만족하는 연산 $\circ$가 주어집니다. 즉, 임의의 $x$, $y$, $z$에 대해 $(x \circ y) \circ z = x \circ (y \circ z)$가 성립합니다.
따라서 $\gcd$, $\min$, $\max$, $+$, $\text{and}$, $\text{or}$, $\text{xor}$ 등의 연산이 이 조건을 만족합니다.
또한 $q(l, r)$ 형태의 쿼리가 여러 개 주어집니다. 각 쿼리마다 $a_l \circ a_{l+1} \circ \dots \circ a_r$을 계산해야 합니다.
Sqrt 트리는 $O(n \cdot \log \log n)$의 전처리 시간과 $O(n \cdot \log \log n)$의 메모리를 사용하여 이러한 쿼리를 $O(1)$ 시간에 처리할 수 있습니다.
설명¶
제곱근 분할법 구성하기¶
제곱근 분할법을 만들어 봅시다. 배열을 $\sqrt{n}$개의 블록으로 나누며, 각 블록의 크기는 $\sqrt{n}$입니다. 각 블록에 대해 다음을 계산합니다:
- 블록 안에 있으면서 블록의 시작에서 시작하는 쿼리들의 답($\text{prefixOp}$)
- 블록 안에 있으면서 블록의 끝에서 끝나는 쿼리들의 답($\text{suffixOp}$)
그리고 추가 배열 하나를 계산합니다:
- $\text{between}_{i, j}$($i \le j$인 경우) - 블록 $i$의 시작에서 시작하여 블록 $j$의 끝에서 끝나는 쿼리의 답입니다. 블록이 $\sqrt{n}$개이므로 이 배열의 크기는 $O(\sqrt{n}^2) = O(n)$이 된다는 점에 유의하십시오.
예시를 살펴봅시다.
$\circ$를 $+$라고 하고(구간의 합을 계산합니다), 다음과 같은 배열 $a$가 있다고 합시다:
{1, 2, 3, 4, 5, 6, 7, 8, 9}
이 배열은 {1, 2, 3}, {4, 5, 6}, {7, 8, 9}의 세 블록으로 나뉩니다.
첫 번째 블록의 $\text{prefixOp}$는 {1, 3, 6}이고 $\text{suffixOp}$는 {6, 5, 3}입니다.
두 번째 블록의 $\text{prefixOp}$는 {4, 9, 15}이고 $\text{suffixOp}$는 {15, 11, 6}입니다.
세 번째 블록의 $\text{prefixOp}$는 {7, 15, 24}이고 $\text{suffixOp}$는 {24, 17, 9}입니다.
$\text{between}$ 배열은 다음과 같습니다:
{
{6, 21, 45},
{0, 15, 39},
{0, 0, 24}
}
($i > j$인 유효하지 않은 원소는 0으로 채워져 있다고 가정합니다)
이 배열들을 $O(n)$의 시간과 메모리로 쉽게 계산할 수 있다는 것은 자명합니다.
이 배열들을 사용하면 이미 일부 쿼리에 답할 수 있습니다. 쿼리가 한 블록 안에 들어가지 않는다면, 쿼리를 세 부분으로 나눌 수 있습니다: 어떤 블록의 접미사, 연속한 블록들로 이루어진 구간, 그리고 어떤 블록의 접두사입니다. 쿼리를 세 부분으로 나눈 뒤 $\text{suffixOp}$의 값 하나, $\text{between}$의 값 하나, $\text{prefixOp}$의 값 하나에 차례로 연산을 적용하여 쿼리에 답할 수 있습니다.
하지만 쿼리가 한 블록 안에 완전히 들어간다면, 이 세 배열로는 처리할 수 없습니다. 따라서 다른 방법이 필요합니다.
트리 만들기¶
다만 하나의 블록에 완전히 들어가는 쿼리에는 답할 수 없습니다. 하지만 각 블록에 대해서도 위에서 설명한 것과 같은 구조를 만들면 어떨까요? 네, 그렇게 할 수 있습니다. 그리고 블록 크기가 $1$ 또는 $2$가 될 때까지 이를 재귀적으로 수행합니다. 이러한 블록에 대한 답은 $O(1)$에 쉽게 계산할 수 있습니다.
이렇게 하면 트리를 얻습니다. 트리의 각 노드는 배열의 어떤 구간을 나타냅니다. 크기가 $k$인 배열 구간을 나타내는 노드는 블록마다 하나씩, $\sqrt{k}$개의 자식을 가집니다. 또한 각 노드는 자신이 담당하는 구간에 대해 위에서 설명한 세 개의 배열을 저장합니다. 트리의 루트는 배열 전체를 나타냅니다. 구간 길이가 $1$ 또는 $2$인 노드는 리프입니다.
또한 이 트리의 높이가 $O(\log \log n)$임은 자명합니다. 트리의 어떤 정점이 길이 $k$인 배열을 나타내면 그 자식들은 길이 $\sqrt{k}$를 가지기 때문입니다. $\log(\sqrt{k}) = \frac{\log{k}}{2}$이므로 $\log k$는 트리의 층마다 절반으로 줄어들고, 따라서 트리의 높이는 $O(\log \log n)$입니다. 배열의 모든 원소는 트리의 각 층에 정확히 한 번씩 나타나므로, 구축 시간과 메모리 사용량은 $O(n \cdot \log \log n)$입니다.
이제 쿼리에 $O(\log \log n)$에 답할 수 있습니다. 길이가 $1$ 또는 $2$인 구간(이에 대한 답은 $O(1)$ 시간에 계산할 수 있습니다)을 만나거나, 쿼리가 하나의 블록에 완전히 들어가지 않는 첫 번째 구간을 만날 때까지 트리를 따라 내려가면 됩니다. 이 경우 쿼리에 답하는 방법은 첫 번째 절을 참고하십시오.
좋습니다, 이제 쿼리당 $O(\log \log n)$에 처리할 수 있습니다. 이보다 더 빠르게 할 수 있을까요?
쿼리 복잡도 최적화¶
가장 명백한 최적화 중 하나는 필요한 트리 노드를 이진 탐색으로 찾는 것입니다. 이진 탐색을 사용하면 쿼리당 $O(\log \log \log n)$의 복잡도에 도달할 수 있습니다. 이보다 더 빠르게 할 수 있을까요?
답은 '그렇다'입니다. 다음 두 가지를 가정합시다.
- 각 블록 크기는 2의 거듭제곱입니다.
- 각 층의 모든 블록은 크기가 같습니다.
이를 위해 배열의 크기가 2의 거듭제곱이 되도록 배열에 0인 원소를 몇 개 추가할 수 있습니다.
이를 사용하면 일부 블록 크기가 2의 거듭제곱이 되기 위해 두 배로 커질 수 있지만, 크기는 여전히 $O(\sqrt{k})$이며 구간 내 배열을 구성하는 데 선형 복잡도를 유지합니다.
이제 쿼리가 크기 $2^k$인 블록에 완전히 들어가는지 쉽게 확인할 수 있습니다. 쿼리의 범위 $l$과 $r$(0-인덱스를 사용합니다)을 이진수로 써 봅시다. 예를 들어 $k=4, l=39, r=46$이라고 가정합시다. $l$과 $r$의 이진 표현은 다음과 같습니다.
$l = 39_{10} = 100111_2$
$r = 46_{10} = 101110_2$
한 레이어에는 같은 크기의 구간들이 들어 있고, 한 레이어의 블록들도 크기가 같다는 점을 기억하십시오(여기서는 블록 크기가 $2^k = 2^4 = 16$입니다. 블록들은 배열 전체를 덮으므로 첫 번째 블록은 원소 $(0 - 15)$(이진수로 $(000000_2 - 001111_2)$)를 덮고, 두 번째 블록은 원소 $(16 - 31)$(이진수로 $(010000_2 - 011111_2)$)를 덮는 식입니다. 한 블록이 덮는 위치의 인덱스들은 마지막 $k$개(여기서는 $4$개) 비트에서만 서로 다를 수 있음을 알 수 있습니다. 여기서 $l$과 $r$은 가장 낮은 네 비트를 제외한 모든 비트가 같으므로 한 블록 안에 있습니다.
따라서 가장 낮은 $k$개 비트 외에는 서로 다른 비트가 없는지(즉, $l\ \text{xor}\ r$이 $2^k-1$을 넘지 않는지) 확인해야 합니다.
이 관찰을 이용하면 쿼리에 빠르게 답하기에 적합한 레이어를 찾을 수 있습니다. 방법은 다음과 같습니다:
-
배열 크기를 넘지 않는 각 $i$에 대해 $1$인 비트 중 가장 높은 비트를 구합니다. 이를 빠르게 하기 위해 DP와 미리 계산한 배열을 사용합니다.
-
이제 각 $q(l, r)$에 대해 $l\ \text{xor}\ r$의 가장 높은 비트를 구하면, 이 정보를 이용해 쿼리를 쉽게 처리할 수 있는 레이어를 쉽게 고를 수 있습니다. 여기서도 미리 계산한 배열을 사용할 수 있습니다.
자세한 내용은 아래 코드를 참고하십시오.
따라서 이를 이용하면 각 쿼리에 $O(1)$에 답할 수 있습니다. 만세! :)
원소 갱신¶
Sqrt 트리에서는 원소를 갱신할 수도 있습니다. 단일 원소 갱신과 구간 갱신을 모두 지원합니다.
단일 원소 갱신¶
대입 $a_x = val$을 수행하는 쿼리 $\text{update}(x, val)$을 생각해 봅시다. 이 쿼리를 충분히 빠르게 수행해야 합니다.
단순한 접근법¶
먼저 원소 하나가 바뀔 때 트리에서 무엇이 바뀌는지 살펴봅시다. 길이가 $l$인 트리 노드와 그 배열 $\text{prefixOp}$, $\text{suffixOp}$, $\text{between}$을 생각해 봅시다. $\text{prefixOp}$과 $\text{suffixOp}$에서는 $O(\sqrt{l})$개의 원소만 바뀐다는 것을 쉽게 알 수 있습니다(바뀐 원소가 있는 블록 안에서만 바뀝니다). $\text{between}$에서는 $O(l)$개의 원소가 바뀝니다. 따라서 트리 노드에서 $O(l)$개의 원소가 갱신됩니다.
어떤 원소 $x$든 각 레이어에서 정확히 하나의 트리 노드에만 들어 있다는 점을 기억합시다. 루트 노드(레이어 $0$)의 길이는 $O(n)$이고, 레이어 $1$의 노드들은 길이가 $O(\sqrt{n})$이며, 레이어 $2$의 노드들은 길이가 $O(\sqrt{\sqrt{n}})$인 식입니다. 따라서 갱신 한 번의 시간 복잡도는 $O(n + \sqrt{n} + \sqrt{\sqrt{n}} + \dots) = O(n)$입니다.
하지만 이는 너무 느립니다. 더 빠르게 할 수 있겠습니까?
sqrt-tree 안의 sqrt-tree¶
갱신의 병목은 루트 노드의 $\text{between}$을 다시 구축하는 부분이라는 점에 유의하십시오. 트리를 최적화하기 위해 이 배열을 없애 봅시다! $\text{between}$ 배열 대신 루트 노드에 또 다른 sqrt 트리를 저장합니다. 이것을 $\text{index}$라고 부릅시다. 이것은 $\text{between}$과 같은 역할을 합니다— 블록 구간에 대한 쿼리에 답합니다. 트리의 나머지 노드에는 $\text{index}$가 없으며, 이 노드들은 각자의 $\text{between}$ 배열을 그대로 유지한다는 점에 유의하십시오.
루트 노드에 $\text{index}$가 있으면 그 sqrt 트리는 인덱싱된 트리입니다. 루트 노드에 $\text{between}$ 배열이 있는 sqrt 트리는 인덱싱되지 않은 트리입니다. $\text{index}$ 자체는 인덱싱되지 않은 트리라는 점에 유의하십시오.
따라서 인덱싱된 트리를 갱신하는 알고리즘은 다음과 같습니다:
-
$\text{prefixOp}$와 $\text{suffixOp}$를 $O(\sqrt{n})$에 갱신합니다.
-
$\text{index}$를 갱신합니다. 그 길이는 $O(\sqrt{n})$이며, 그 안에서 (변경된 블록을 나타내는) 항목 하나만 갱신하면 됩니다. 따라서 이 단계의 시간 복잡도는 $O(\sqrt{n})$입니다. 이를 위해 이 절의 처음에 설명한 ("느린") 알고리즘을 사용할 수 있습니다.
-
변경된 블록을 나타내는 자식 노드로 들어가 "느린" 알고리즘으로 $O(\sqrt{n})$에 갱신합니다.
쿼리 복잡도는 여전히 $O(1)$이라는 점에 유의하십시오: 쿼리에서 $\text{index}$는 최대 한 번만 사용하며, 이는 $O(1)$ 시간이 걸립니다.
따라서 원소 하나를 갱신하는 전체 시간 복잡도는 $O(\sqrt{n})$입니다. 만세! :)
구간 갱신¶
sqrt 트리는 구간에 원소를 대입하는 것과 같은 작업도 할 수 있습니다. $\text{massUpdate}(x, l, r)$는 모든 $l \le i \le r$에 대해 $a_i = x$로 만드는 것을 의미합니다.
이를 수행하는 방법은 두 가지입니다: 하나는 쿼리당 $O(1)$을 유지하면서 $\text{massUpdate}$를 $O(\sqrt{n}\cdot \log \log n)$에 수행합니다. 다른 하나는 $\text{massUpdate}$를 $O(\sqrt{n})$에 수행하지만, 쿼리 복잡도가 $O(\log \log n)$이 됩니다.
세그먼트 트리에서와 같은 방식으로 지연 전파를 수행합니다: 일부 노드를 lazy 상태로 표시하며, 이는 필요할 때 해당 노드를 push한다는 뜻입니다. 하지만 세그먼트 트리와 다른 점이 하나 있습니다: 노드를 push하는 비용이 크기 때문에 쿼리 중에는 수행할 수 없습니다. 레이어 $0$에서 노드를 push하는 데는 $O(\sqrt{n})$ 시간이 걸립니다. 따라서 쿼리 안에서는 노드를 push하지 않고, 현재 노드나 그 부모가 lazy 상태인지만 확인하여 쿼리를 수행할 때 이를 고려합니다.
첫 번째 방법¶
첫 번째 방법에서는 레이어 $1$에 있는 (길이가 $O(\sqrt{n}$인) 노드만 lazy 상태가 될 수 있다고 합니다. 이러한 노드를 push할 때는 자기 자신을 포함한 서브트리 전체를 $O(\sqrt{n}\cdot \log \log n)$에 갱신합니다. $\text{massUpdate}$ 과정은 다음과 같이 수행됩니다:
-
레이어 $1$의 노드들과 그에 대응하는 블록들을 살펴봅시다.
-
일부 블록은 $\text{massUpdate}$에 의해 완전히 덮입니다. 이 블록들을 $O(\sqrt{n})$에 lazy로 표시합니다.
-
일부 블록은 부분적으로 덮입니다. 이러한 블록은 두 개를 넘지 않는다는 점에 유의하십시오. 이 블록들을 $O(\sqrt{n}\cdot \log \log n)$에 다시 구축합니다. 이 블록들이 lazy였다면 이를 반영하십시오.
-
부분적으로 덮인 블록에 대해 $\text{prefixOp}$와 $\text{suffixOp}$를 $O(\sqrt{n})$에 갱신합니다(이러한 블록은 두 개뿐이기 때문입니다).
-
$\text{index}$를 $O(\sqrt{n}\cdot \log \log n)$에 다시 구축합니다.
따라서 $\text{massUpdate}$를 빠르게 수행할 수 있습니다. 그렇다면 지연 전파는 쿼리에 어떤 영향을 미칩니까? 쿼리는 다음과 같이 수정됩니다.
-
쿼리가 lazy 블록 안에 완전히 놓인다면, 쿼리를 계산하되 lazy를 반영하십시오. $O(1)$입니다.
-
쿼리가 여러 블록으로 이루어져 있고 그중 일부가 lazy 상태라면, 가장 왼쪽 블록과 가장 오른쪽 블록에서만 lazy를 처리하면 됩니다. 나머지 블록은 $\text{index}$를 사용하여 계산하는데, $\text{index}$는 매 수정 후 다시 구축되므로 lazy 블록에 대한 답을 이미 알고 있습니다. $O(1)$입니다.
쿼리 복잡도는 여전히 $O(1)$입니다.
두 번째 접근법¶
이 접근법에서는 루트를 제외한 각 노드가 lazy일 수 있습니다. $\text{index}$ 안의 노드조차 lazy일 수 있습니다. 따라서 쿼리를 처리하는 동안 모든 부모 노드에서 lazy 태그를 확인해야 하므로, 쿼리 복잡도는 $O(\log \log n)$이 됩니다.
하지만 $\text{massUpdate}$는 더 빨라집니다. 그 방식은 다음과 같습니다.
-
일부 블록은 $\text{massUpdate}$에 의해 완전히 덮입니다. 따라서 이 블록들에 lazy 태그를 추가합니다. 이는 $O(\sqrt{n})$입니다.
-
부분적으로 덮인 블록에 대해 $\text{prefixOp}$와 $\text{suffixOp}$를 $O(\sqrt{n})$에 갱신합니다(이러한 블록은 두 개뿐이기 때문입니다).
-
인덱스를 갱신하는 것을 잊지 마십시오. 이는 $O(\sqrt{n})$입니다(같은 $\text{massUpdate}$ 알고리즘을 사용합니다).
-
unindexed 서브트리에 대해 $\text{between}$ 배열을 갱신합니다.
-
부분적으로 덮인 블록을 나타내는 노드로 들어가 $\text{massUpdate}$를 재귀적으로 호출합니다.
재귀 호출을 할 때 접두사 또는 접미사 $\text{massUpdate}$를 수행한다는 점에 유의하십시오. 그런데 접두사 및 접미사 업데이트에서는 부분적으로 덮이는 자식이 최대 하나뿐입니다. 따라서 계층 $1$에서는 노드 하나를, 계층 $2$에서는 노드 두 개를, 그보다 깊은 모든 계층에서는 노드 두 개를 방문합니다. 따라서 시간 복잡도는 $O(\sqrt{n} + \sqrt{\sqrt{n}} + \dots) = O(\sqrt{n})$입니다. 이 접근 방식은 세그먼트 트리의 대량 업데이트와 유사합니다.
구현¶
다음 Sqrt 트리 구현은 다음 연산을 수행할 수 있습니다: $O(n \cdot \log \log n)$에 구성, $O(1)$에 쿼리 응답, $O(\sqrt{n})$에 원소 갱신.
SqrtTreeItem op(const SqrtTreeItem &a, const SqrtTreeItem &b);
inline int log2Up(int n) {
int res = 0;
while ((1 << res) < n) {
res++;
}
return res;
}
class SqrtTree {
private:
int n, lg, indexSz;
vector<SqrtTreeItem> v;
vector<int> clz, layers, onLayer;
vector< vector<SqrtTreeItem> > pref, suf, between;
inline void buildBlock(int layer, int l, int r) {
pref[layer][l] = v[l];
for (int i = l+1; i < r; i++) {
pref[layer][i] = op(pref[layer][i-1], v[i]);
}
suf[layer][r-1] = v[r-1];
for (int i = r-2; i >= l; i--) {
suf[layer][i] = op(v[i], suf[layer][i+1]);
}
}
inline void buildBetween(int layer, int lBound, int rBound, int betweenOffs) {
int bSzLog = (layers[layer]+1) >> 1;
int bCntLog = layers[layer] >> 1;
int bSz = 1 << bSzLog;
int bCnt = (rBound - lBound + bSz - 1) >> bSzLog;
for (int i = 0; i < bCnt; i++) {
SqrtTreeItem ans;
for (int j = i; j < bCnt; j++) {
SqrtTreeItem add = suf[layer][lBound + (j << bSzLog)];
ans = (i == j) ? add : op(ans, add);
between[layer-1][betweenOffs + lBound + (i << bCntLog) + j] = ans;
}
}
}
inline void buildBetweenZero() {
int bSzLog = (lg+1) >> 1;
for (int i = 0; i < indexSz; i++) {
v[n+i] = suf[0][i << bSzLog];
}
build(1, n, n + indexSz, (1 << lg) - n);
}
inline void updateBetweenZero(int bid) {
int bSzLog = (lg+1) >> 1;
v[n+bid] = suf[0][bid << bSzLog];
update(1, n, n + indexSz, (1 << lg) - n, n+bid);
}
void build(int layer, int lBound, int rBound, int betweenOffs) {
if (layer >= (int)layers.size()) {
return;
}
int bSz = 1 << ((layers[layer]+1) >> 1);
for (int l = lBound; l < rBound; l += bSz) {
int r = min(l + bSz, rBound);
buildBlock(layer, l, r);
build(layer+1, l, r, betweenOffs);
}
if (layer == 0) {
buildBetweenZero();
} else {
buildBetween(layer, lBound, rBound, betweenOffs);
}
}
void update(int layer, int lBound, int rBound, int betweenOffs, int x) {
if (layer >= (int)layers.size()) {
return;
}
int bSzLog = (layers[layer]+1) >> 1;
int bSz = 1 << bSzLog;
int blockIdx = (x - lBound) >> bSzLog;
int l = lBound + (blockIdx << bSzLog);
int r = min(l + bSz, rBound);
buildBlock(layer, l, r);
if (layer == 0) {
updateBetweenZero(blockIdx);
} else {
buildBetween(layer, lBound, rBound, betweenOffs);
}
update(layer+1, l, r, betweenOffs, x);
}
inline SqrtTreeItem query(int l, int r, int betweenOffs, int base) {
if (l == r) {
return v[l];
}
if (l + 1 == r) {
return op(v[l], v[r]);
}
int layer = onLayer[clz[(l - base) ^ (r - base)]];
int bSzLog = (layers[layer]+1) >> 1;
int bCntLog = layers[layer] >> 1;
int lBound = (((l - base) >> layers[layer]) << layers[layer]) + base;
int lBlock = ((l - lBound) >> bSzLog) + 1;
int rBlock = ((r - lBound) >> bSzLog) - 1;
SqrtTreeItem ans = suf[layer][l];
if (lBlock <= rBlock) {
SqrtTreeItem add = (layer == 0) ? (
query(n + lBlock, n + rBlock, (1 << lg) - n, n)
) : (
between[layer-1][betweenOffs + lBound + (lBlock << bCntLog) + rBlock]
);
ans = op(ans, add);
}
ans = op(ans, pref[layer][r]);
return ans;
}
public:
inline SqrtTreeItem query(int l, int r) {
return query(l, r, 0, 0);
}
inline void update(int x, const SqrtTreeItem &item) {
v[x] = item;
update(0, 0, n, 0, x);
}
SqrtTree(const vector<SqrtTreeItem>& a)
: n((int)a.size()), lg(log2Up(n)), v(a), clz(1 << lg), onLayer(lg+1) {
clz[0] = 0;
for (int i = 1; i < (int)clz.size(); i++) {
clz[i] = clz[i >> 1] + 1;
}
int tlg = lg;
while (tlg > 1) {
onLayer[tlg] = (int)layers.size();
layers.push_back(tlg);
tlg = (tlg+1) >> 1;
}
for (int i = lg-1; i >= 0; i--) {
onLayer[i] = max(onLayer[i], onLayer[i+1]);
}
int betweenLayers = max(0, (int)layers.size() - 1);
int bSzLog = (lg+1) >> 1;
int bSz = 1 << bSzLog;
indexSz = (n + bSz - 1) >> bSzLog;
v.resize(n + indexSz);
pref.assign(layers.size(), vector<SqrtTreeItem>(n + indexSz));
suf.assign(layers.size(), vector<SqrtTreeItem>(n + indexSz));
between.assign(betweenLayers, vector<SqrtTreeItem>((1 << lg) + bSz));
build(0, 0, n, 0);
}
};