Range Query Problems, Mo's Algorithm and Rollback Square Root Decomposition

日付: 11月 21, 2018

It quite often to encounter range query problems. Some of them can be solved with data structures such as segment trees, but some cannot (when answer of incident ranges cannot be merged). In this case we should consider converting queries **offline** and solve them.

## Mo's Algorithm
**Prerequirements: it is possible to update answer of the range when add/delete one element at the left/right side**

If the above condition is satisfied, we can reduce time complexity from $O(N^2)$ to $O(N\sqrt N)$ by just change the order of queries.

Fistly we divide the whole length into some blocks, each has length $\sqrt N$. We define that a query belongs to some block if its left side is in that block, and sort queries first by its block, then by its right side, increasingly.

Let's do a simple analysis. 
1. For each block, the right side is sorted increasingly, so the number of moves of the right side is $O(N)$, in total $O(N\sqrt N)$.  
2. For each query, the number of moves of the left side is $O(\sqrt N)$ (they are in the same block or in adjacent blocks). In total $O(N\sqrt N)$

The number of moves of both left side and right side of the range are $O(N\sqrt N)$, so the total time complexity is also $O(N\sqrt N)$, if add/delete operation is $O(1)$.

And a simple optimization exists: for each block, alternating between increasing and decreasing the right side.
```c++
    const int N;
    int n;
    vector<int> L(n), R(n); // Queries
    vector<int> I(n); // Index of queries
    int qn = sqrt(N); // Block size
    iota(I.begin(), I.end(), 0);
    sort(I.begin(), I.end(), [&](int i, int j) {
        return L[i] / qn == L[j] / qn ? 
            (L[i] / qn & 1 ? R[i] > R[j] : R[i] < R[j]) : L[i] < L[j];
    });
    // add(i) add element to range
    // del(i) delete element to range
    int cl = 0, cr = 0;
    for (int i : I) {
        while (cl > L[i]) add(--cl);
        while (cr < R[i]) add(cr++);
        while (cl < L[i]) del(cl++);
        while (cr > R[i]) del(--cr);
        // calculate answer for query q
    }
```
## Rollback Square Root Decomposition
Sometimes the **deletion** operations are not tackleable.

The query sorting strategy is just as Mo's algorithm. For queries whose length is not longer than $\sqrt N$, just calculate directly.
For every block, the range from the right side of the block, and add elements one by one in the right side. When reaches some right side with queries, take a **snapshot** of the current state, and add element to the left until reaches the left side of the block, then **rollback** to the snapshot and continue.

KONGROOの基地

このブログを検索

Range Query Problems, Mo's Algorithm and Rollback Square Root Decomposition

コメント

コメントを投稿