Square Root Decomposition

Square root decomposition divides data into √n blocks, allowing efficient updates and queries. This technique balances between simple arrays and complex data structures.

Basic Square Root Decomposition

class SqrtDecomposition {
private:
    vector<int> arr, blocks;
    int n, blockSize, numBlocks;
    
public:
    SqrtDecomposition(vector<int>& data) {
        arr = data;
        n = arr.size();
        blockSize = sqrt(n) + 1;
        numBlocks = (n + blockSize - 1) / blockSize;
        blocks.assign(numBlocks, 0);
        
        // Precompute block sums
        for(int i = 0; i < n; i++) {
            blocks[i / blockSize] += arr[i];
        }
    }
    
    // Point update: arr[idx] += val
    void update(int idx, int val) {
        arr[idx] += val;
        blocks[idx / blockSize] += val;
    }
    
    // Range query: sum of arr[l..r]
    long long query(int l, int r) {
        long long sum = 0;
        int startBlock = l / blockSize;
        int endBlock = r / blockSize;
        
        if(startBlock == endBlock) {
            // Query within single block
            for(int i = l; i <= r; i++) {
                sum += arr[i];
            }
        } else {
            // Handle partial blocks at start and end
            for(int i = l; i < (startBlock + 1) * blockSize; i++) {
                sum += arr[i];
            }
            
            // Handle complete blocks in middle
            for(int block = startBlock + 1; block < endBlock; block++) {
                sum += blocks[block];
            }
            
            // Handle partial block at end
            for(int i = endBlock * blockSize; i <= r; i++) {
                sum += arr[i];
            }
        }
        
        return sum;
    }
    
    // Range update: add val to arr[l..r]
    void rangeUpdate(int l, int r, int val) {
        int startBlock = l / blockSize;
        int endBlock = r / blockSize;
        
        if(startBlock == endBlock) {
            // Update within single block
            for(int i = l; i <= r; i++) {
                arr[i] += val;
            }
            blocks[startBlock] += val * (r - l + 1);
        } else {
            // Handle partial blocks
            for(int i = l; i < (startBlock + 1) * blockSize; i++) {
                arr[i] += val;
                blocks[startBlock] += val;
            }
            
            // Handle complete blocks
            for(int block = startBlock + 1; block < endBlock; block++) {
                blocks[block] += val * blockSize;
                // Note: Individual elements updated lazily
            }
            
            // Handle partial block at end
            for(int i = endBlock * blockSize; i <= r; i++) {
                arr[i] += val;
                blocks[endBlock] += val;
            }
        }
    }
};
                    

Mo's Algorithm

Mo's algorithm efficiently processes offline range queries by reordering them to minimize the total cost of extending/contracting the current range.

Basic Mo's Algorithm Template

struct Query {
    int l, r, idx;
    int block;
    
    Query(int l, int r, int idx, int blockSize) : l(l), r(r), idx(idx) {
        block = l / blockSize;
    }
    
    bool operator<(const Query& other) const {
        if(block != other.block) return block < other.block;
        return (block & 1) ? r < other.r : r > other.r; // Optimization
    }
};

class MoAlgorithm {
private:
    vector<int> arr;
    vector<int> freq; // Frequency of each element
    int currentAnswer;
    
    void add(int pos) {
        int val = arr[pos];
        // Update current answer when adding arr[pos]
        currentAnswer -= freq[val] * freq[val] * val;
        freq[val]++;
        currentAnswer += freq[val] * freq[val] * val;
    }
    
    void remove(int pos) {
        int val = arr[pos];
        // Update current answer when removing arr[pos]
        currentAnswer -= freq[val] * freq[val] * val;
        freq[val]--;
        currentAnswer += freq[val] * freq[val] * val;
    }
    
public:
    MoAlgorithm(vector<int>& data) : arr(data), currentAnswer(0) {
        int maxVal = *max_element(arr.begin(), arr.end());
        freq.assign(maxVal + 1, 0);
    }
    
    vector<int> processQueries(vector<Query>& queries) {
        int blockSize = sqrt(arr.size()) + 1;
        
        // Set block for each query and sort
        for(auto& q : queries) {
            q.block = q.l / blockSize;
        }
        sort(queries.begin(), queries.end());
        
        vector<int> answers(queries.size());
        int currL = 0, currR = -1;
        
        for(auto& query : queries) {
            // Extend/contract current range to match query range
            while(currR < query.r) {
                currR++;
                add(currR);
            }
            while(currR > query.r) {
                remove(currR);
                currR--;
            }
            while(currL < query.l) {
                remove(currL);
                currL++;
            }
            while(currL > query.l) {
                currL--;
                add(currL);
            }
            
            answers[query.idx] = currentAnswer;
        }
        
        return answers;
    }
};

// Example usage: Count distinct elements in range
class DistinctMo {
private:
    vector<int> arr, freq;
    int distinctCount;
    
    void add(int pos) {
        if(freq[arr[pos]] == 0) distinctCount++;
        freq[arr[pos]]++;
    }
    
    void remove(int pos) {
        freq[arr[pos]]--;
        if(freq[arr[pos]] == 0) distinctCount--;
    }
    
public:
    DistinctMo(vector<int>& data) : arr(data), distinctCount(0) {
        int maxVal = *max_element(arr.begin(), arr.end());
        freq.assign(maxVal + 1, 0);
    }
    
    vector<int> solve(vector<pair<int, int>>& queryRanges) {
        vector<Query> queries;
        int blockSize = sqrt(arr.size()) + 1;
        
        for(int i = 0; i < queryRanges.size(); i++) {
            queries.emplace_back(queryRanges[i].first, queryRanges[i].second, i, blockSize);
        }
        
        sort(queries.begin(), queries.end());
        
        vector<int> answers(queries.size());
        int currL = 0, currR = -1;
        
        for(auto& query : queries) {
            while(currR < query.r) add(++currR);
            while(currR > query.r) remove(currR--);
            while(currL < query.l) remove(currL++);
            while(currL > query.l) add(--currL);
            
            answers[query.idx] = distinctCount;
        }
        
        return answers;
    }
};
                    

Advanced Square Root Techniques

Square Root with Lazy Propagation

class LazySquareRoot {
private:
    vector<int> arr, lazy;
    int n, blockSize, numBlocks;
    
public:
    LazySquareRoot(vector<int>& data) {
        arr = data;
        n = arr.size();
        blockSize = sqrt(n) + 1;
        numBlocks = (n + blockSize - 1) / blockSize;
        lazy.assign(numBlocks, 0);
    }
    
    void rangeUpdate(int l, int r, int val) {
        int startBlock = l / blockSize;
        int endBlock = r / blockSize;
        
        if(startBlock == endBlock) {
            // Update within single block
            for(int i = l; i <= r; i++) {
                arr[i] += val;
            }
        } else {
            // Handle partial blocks
            for(int i = l; i < (startBlock + 1) * blockSize; i++) {
                arr[i] += val;
            }
            
            // Handle complete blocks with lazy propagation
            for(int block = startBlock + 1; block < endBlock; block++) {
                lazy[block] += val;
            }
            
            // Handle end block
            for(int i = endBlock * blockSize; i <= r; i++) {
                arr[i] += val;
            }
        }
    }
    
    int pointQuery(int idx) {
        return arr[idx] + lazy[idx / blockSize];
    }
    
    long long rangeQuery(int l, int r) {
        long long sum = 0;
        
        for(int i = l; i <= r; i++) {
            sum += pointQuery(i);
        }
        
        return sum;
    }
};
                    

Sqrt Tree (Advanced)

class SqrtTree {
private:
    vector<vector<int>> tree;
    vector<int> arr;
    int n, levels;
    
    void build(int level, int l, int r) {
        if(level == 0) {
            tree[level].assign(arr.begin() + l, arr.begin() + r + 1);
            return;
        }
        
        int blockSize = sqrt(r - l + 1);
        int blocks = (r - l + 1 + blockSize - 1) / blockSize;
        
        tree[level].assign(blocks, 0);
        
        for(int i = 0; i < blocks; i++) {
            int start = l + i * blockSize;
            int end = min(r, start + blockSize - 1);
            
            // Compute block value (e.g., sum, min, max)
            for(int j = start; j <= end; j++) {
                tree[level][i] += arr[j];
            }
            
            if(level > 1) {
                build(level - 1, start, end);
            }
        }
    }
    
public:
    SqrtTree(vector<int>& data) : arr(data), n(data.size()) {
        levels = 0;
        int temp = n;
        while(temp > 1) {
            temp = sqrt(temp) + 1;
            levels++;
        }
        
        tree.resize(levels + 1);
        build(levels, 0, n - 1);
    }
    
    // Query implementation would be complex and depend on specific operation
    int query(int l, int r) {
        // Simplified version - would need full implementation
        return rangeSum(l, r, levels, 0, n - 1);
    }
    
private:
    int rangeSum(int l, int r, int level, int treeL, int treeR) {
        if(level == 0) {
            int sum = 0;
            for(int i = l - treeL; i <= r - treeL; i++) {
                sum += tree[level][i];
            }
            return sum;
        }
        
        int blockSize = sqrt(treeR - treeL + 1);
        int startBlock = (l - treeL) / blockSize;
        int endBlock = (r - treeL) / blockSize;
        
        int sum = 0;
        
        if(startBlock == endBlock) {
            int blockStart = treeL + startBlock * blockSize;
            int blockEnd = min(treeR, blockStart + blockSize - 1);
            return rangeSum(l, r, level - 1, blockStart, blockEnd);
        }
        
        // Handle multiple blocks (simplified)
        for(int block = startBlock; block <= endBlock; block++) {
            if(block == startBlock || block == endBlock) {
                int blockStart = treeL + block * blockSize;
                int blockEnd = min(treeR, blockStart + blockSize - 1);
                int queryStart = max(l, blockStart);
                int queryEnd = min(r, blockEnd);
                sum += rangeSum(queryStart, queryEnd, level - 1, blockStart, blockEnd);
            } else {
                sum += tree[level][block];
            }
        }
        
        return sum;
    }
};
                    

Applications and Optimizations

Mo's Algorithm with Updates

// Mo's algorithm with updates (Mo's with time)
struct QueryWithTime {
    int l, r, time, idx;
    
    bool operator<(const QueryWithTime& other) const {
        int block1 = l / BLOCK_SIZE;
        int block2 = other.l / BLOCK_SIZE;
        
        if(block1 != block2) return block1 < block2;
        
        int block_r1 = r / BLOCK_SIZE;
        int block_r2 = other.r / BLOCK_SIZE;
        
        if(block_r1 != block_r2) return block_r1 < block_r2;
        
        return time < other.time;
    }
};

// Mo's for tree paths
class TreeMo {
private:
    vector<vector<int>> adj;
    vector<int> first, last, depth, euler;
    vector<bool> visited;
    int timer;
    
    void dfs(int u, int d) {
        visited[u] = true;
        first[u] = timer;
        euler[timer++] = u;
        depth[u] = d;
        
        for(int v : adj[u]) {
            if(!visited[v]) {
                dfs(v, d + 1);
            }
        }
        
        last[u] = timer;
        euler[timer++] = u;
    }
    
public:
    TreeMo(int n, vector<vector<int>>& tree) : adj(tree), timer(0) {
        first.resize(n);
        last.resize(n);
        depth.resize(n);
        euler.resize(2 * n);
        visited.resize(n);
        
        dfs(0, 0);
    }
    
    pair<int, int> getPathRange(int u, int v) {
        // Convert tree path query to range query on Euler tour
        if(first[u] > first[v]) swap(u, v);
        return {first[u], first[v]};
    }
};