Square Root Decomposition

1. Range Query Block Division

Concept	Description	Complexity	Use Case
Block Size	Divide array of size n into √n blocks, each of size √n	`O(√n)`	Balance between query and update time
Block Storage	Store precomputed values for each block (sum, min, max, etc.)	Space: `O(√n)`	Fast block-level queries
Range Query	Combine full blocks + partial blocks at boundaries	`O(√n)`	Sum/min/max over range [L, R]
Point Update	Update single element + update its block's precomputed value	`O(1)`	Modify single array element

Example: Range sum query with updates

class SqrtDecomposition {
    constructor(arr) {
        this.arr = [...arr];
        this.n = arr.length;
        this.blockSize = Math.floor(Math.sqrt(this.n));
        this.numBlocks = Math.ceil(this.n / this.blockSize);
        this.blocks = new Array(this.numBlocks).fill(0);
        
        // Build block sums
        for (let i = 0; i < this.n; i++) {
            const blockIdx = Math.floor(i / this.blockSize);
            this.blocks[blockIdx] += arr[i];
        }
    }
    
    // Update value at index
    update(idx, val) {
        const blockIdx = Math.floor(idx / this.blockSize);
        this.blocks[blockIdx] += val - this.arr[idx];
        this.arr[idx] = val;
    }
    
    // Query sum in range [left, right]
    query(left, right) {
        let sum = 0;
        const leftBlock = Math.floor(left / this.blockSize);
        const rightBlock = Math.floor(right / this.blockSize);
        
        if (leftBlock === rightBlock) {
            // Both in same block - iterate elements
            for (let i = left; i <= right; i++) {
                sum += this.arr[i];
            }
        } else {
            // Left partial block
            const leftEnd = (leftBlock + 1) * this.blockSize - 1;
            for (let i = left; i <= leftEnd; i++) {
                sum += this.arr[i];
            }
            
            // Full blocks in middle
            for (let b = leftBlock + 1; b < rightBlock; b++) {
                sum += this.blocks[b];
            }
            
            // Right partial block
            const rightStart = rightBlock * this.blockSize;
            for (let i = rightStart; i <= right; i++) {
                sum += this.arr[i];
            }
        }
        
        return sum;
    }
}

// Example usage
const arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
const sqd = new SqrtDecomposition(arr);
console.log(sqd.query(2, 7)); // Sum of [5,7,9,11,13,15] = 60
sqd.update(5, 20); // Change 11 to 20
console.log(sqd.query(2, 7)); // Sum now = 69

2. Mo's Algorithm Query Ordering

Concept	Strategy	Complexity	Application
Query Reordering	Process queries in special order to minimize pointer movements	`O((n + q)√n)`	Offline query processing
Block Sorting	Sort queries by (left/√n, right) - primary by left block, secondary by right	Sort: `O(q log q)`	Group queries by left block
Add/Remove	Maintain current range [L, R], expand/contract to match each query	Per query: `O(√n)`	Incrementally update answer
State Tracking	Keep frequency map or other structure for current range	Space: `O(n)`	Track distinct elements, frequencies, etc.

Example: Mo's Algorithm - Distinct elements in ranges

function mosAlgorithm(arr, queries) {
    const n = arr.length;
    const q = queries.length;
    const blockSize = Math.floor(Math.sqrt(n));
    
    // Add index to each query and sort
    const indexedQueries = queries.map((query, idx) => ({
        left: query[0],
        right: query[1],
        idx: idx
    }));
    
    // Sort queries by block of left, then by right
    indexedQueries.sort((a, b) => {
        const blockA = Math.floor(a.left / blockSize);
        const blockB = Math.floor(b.left / blockSize);
        if (blockA !== blockB) return blockA - blockB;
        return a.right - b.right;
    });
    
    const result = new Array(q);
    const freq = new Map();
    let distinctCount = 0;
    let currLeft = 0, currRight = -1;
    
    // Helper functions
    function add(idx) {
        const val = arr[idx];
        const count = freq.get(val) || 0;
        if (count === 0) distinctCount++;
        freq.set(val, count + 1);
    }
    
    function remove(idx) {
        const val = arr[idx];
        const count = freq.get(val);
        if (count === 1) distinctCount--;
        freq.set(val, count - 1);
    }
    
    // Process queries in sorted order
    for (const query of indexedQueries) {
        const {left, right, idx} = query;
        
        // Expand/contract current range to match query range
        while (currRight < right) {
            currRight++;
            add(currRight);
        }
        while (currRight > right) {
            remove(currRight);
            currRight--;
        }
        while (currLeft < left) {
            remove(currLeft);
            currLeft++;
        }
        while (currLeft > left) {
            currLeft--;
            add(currLeft);
        }
        
        result[idx] = distinctCount;
    }
    
    return result;
}

// Example
const arr = [1, 1, 2, 1, 3, 4, 5, 2, 8];
const queries = [[0, 4], [0, 8], [2, 5]];
console.log(mosAlgorithm(arr, queries)); 
// [3, 6, 4] - distinct elements in each range

Note: Mo's algorithm is offline - all queries must be known beforehand. The key insight: sorting queries by blocks minimizes L/R pointer movements from O(n×q) to O((n+q)√n).

3. Update Query Trade-off

Structure	Query Time	Update Time	Best For
Plain Array	`O(n)` range query	`O(1)` update	Many updates, few queries
Prefix Sum	`O(1)` range query	`O(n)` rebuild	Static data, many queries
Sqrt Decomposition	`O(√n)` range query	`O(1)` update	Balanced queries and updates
Segment Tree	`O(log n)` query	`O(log n)` update	Best overall, more complex
Fenwick Tree (BIT)	`O(log n)` query	`O(log n)` update	Simple implementation, prefix queries

Example: Range minimum with updates

class SqrtMinQuery {
    constructor(arr) {
        this.arr = [...arr];
        this.n = arr.length;
        this.blockSize = Math.floor(Math.sqrt(this.n));
        this.numBlocks = Math.ceil(this.n / this.blockSize);
        this.blockMin = new Array(this.numBlocks).fill(Infinity);
        
        this.buildBlocks();
    }
    
    buildBlocks() {
        for (let i = 0; i < this.n; i++) {
            const blockIdx = Math.floor(i / this.blockSize);
            this.blockMin[blockIdx] = Math.min(
                this.blockMin[blockIdx], 
                this.arr[i]
            );
        }
    }
    
    update(idx, val) {
        this.arr[idx] = val;
        // Rebuild affected block
        const blockIdx = Math.floor(idx / this.blockSize);
        const start = blockIdx * this.blockSize;
        const end = Math.min(start + this.blockSize, this.n);
        
        this.blockMin[blockIdx] = Infinity;
        for (let i = start; i < end; i++) {
            this.blockMin[blockIdx] = Math.min(
                this.blockMin[blockIdx], 
                this.arr[i]
            );
        }
    }
    
    queryMin(left, right) {
        let minVal = Infinity;
        const leftBlock = Math.floor(left / this.blockSize);
        const rightBlock = Math.floor(right / this.blockSize);
        
        if (leftBlock === rightBlock) {
            for (let i = left; i <= right; i++) {
                minVal = Math.min(minVal, this.arr[i]);
            }
        } else {
            // Left partial
            const leftEnd = (leftBlock + 1) * this.blockSize - 1;
            for (let i = left; i <= leftEnd; i++) {
                minVal = Math.min(minVal, this.arr[i]);
            }
            
            // Middle full blocks
            for (let b = leftBlock + 1; b < rightBlock; b++) {
                minVal = Math.min(minVal, this.blockMin[b]);
            }
            
            // Right partial
            const rightStart = rightBlock * this.blockSize;
            for (let i = rightStart; i <= right; i++) {
                minVal = Math.min(minVal, this.arr[i]);
            }
        }
        
        return minVal;
    }
}

const arr = [5, 2, 8, 1, 9, 3, 7, 4, 6];
const smq = new SqrtMinQuery(arr);
console.log(smq.queryMin(2, 6)); // 1
smq.update(3, 10);
console.log(smq.queryMin(2, 6)); // 3

Complexity Comparison

Operation	Sqrt Decomp	Segment Tree
Build	`O(n)`	`O(n)`
Query	`O(√n)`	`O(log n)`
Update	`O(1)` or `O(√n)`	`O(log n)`
Space	`O(n + √n)`	`O(2n)`
Implementation	Simple	More complex

Note: Choose sqrt decomposition when:

Implementation simplicity matters
√n performance is acceptable
Segment tree seems overkill

4. Sqrt Decomposition on Arrays

Application	Block Storage	Query Operation	Example Problem
Range Sum	Sum of each block	Sum full blocks + partial blocks at ends	Sum of elements in range [L, R]
Range Min/Max	Min/Max of each block	Min/Max across blocks + check partial blocks	Minimum element in range
Range GCD	GCD of each block	GCD of full blocks + partial blocks	GCD of range elements
Distinct Count	Frequency map per block	Merge frequencies from relevant blocks	Count distinct in range
Range Update	Lazy propagation flag per block	Apply lazy updates when querying	Add value to all elements in range

Example: Range GCD queries

function gcd(a, b) {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}

class RangeGCD {
    constructor(arr) {
        this.arr = [...arr];
        this.n = arr.length;
        this.blockSize = Math.floor(Math.sqrt(this.n));
        this.numBlocks = Math.ceil(this.n / this.blockSize);
        this.blockGCD = new Array(this.numBlocks).fill(0);
        
        // Build block GCDs
        for (let i = 0; i < this.n; i++) {
            const blockIdx = Math.floor(i / this.blockSize);
            this.blockGCD[blockIdx] = gcd(this.blockGCD[blockIdx], arr[i]);
        }
    }
    
    query(left, right) {
        let result = 0;
        const leftBlock = Math.floor(left / this.blockSize);
        const rightBlock = Math.floor(right / this.blockSize);
        
        if (leftBlock === rightBlock) {
            // Same block
            for (let i = left; i <= right; i++) {
                result = gcd(result, this.arr[i]);
            }
        } else {
            // Left partial block
            const leftEnd = (leftBlock + 1) * this.blockSize - 1;
            for (let i = left; i <= leftEnd; i++) {
                result = gcd(result, this.arr[i]);
            }
            
            // Full blocks
            for (let b = leftBlock + 1; b < rightBlock; b++) {
                result = gcd(result, this.blockGCD[b]);
            }
            
            // Right partial block
            const rightStart = rightBlock * this.blockSize;
            for (let i = rightStart; i <= right; i++) {
                result = gcd(result, this.arr[i]);
            }
        }
        
        return result;
    }
}

const arr = [2, 4, 6, 8, 10, 12, 14, 16];
const rgcd = new RangeGCD(arr);
console.log(rgcd.query(0, 3)); // gcd(2,4,6,8) = 2
console.log(rgcd.query(2, 5)); // gcd(6,8,10,12) = 2

5. Block-wise Processing Pattern

Pattern	Technique	Benefit	Use Case
Batch Processing	Group operations into blocks, process entire blocks together	Cache efficiency, reduced overhead	Matrix operations, image processing
Lazy Propagation	Mark blocks as modified, apply changes only when needed	Defer expensive operations	Range update queries
Block Rebuilding	When block updates exceed threshold, rebuild entire block	Amortized efficiency	Dynamic data with occasional updates
Sqrt Partitioning	Divide problems into √n groups for balanced complexity	Optimal space-time trade-off	Query optimization problems

Example: Range add with lazy propagation

class RangeAddQuery {
    constructor(arr) {
        this.arr = [...arr];
        this.n = arr.length;
        this.blockSize = Math.floor(Math.sqrt(this.n));
        this.numBlocks = Math.ceil(this.n / this.blockSize);
        this.lazy = new Array(this.numBlocks).fill(0); // Lazy values
    }
    
    // Add value to range [left, right]
    rangeAdd(left, right, val) {
        const leftBlock = Math.floor(left / this.blockSize);
        const rightBlock = Math.floor(right / this.blockSize);
        
        if (leftBlock === rightBlock) {
            // Same block - update individually
            for (let i = left; i <= right; i++) {
                this.arr[i] += val;
            }
        } else {
            // Left partial block
            const leftEnd = (leftBlock + 1) * this.blockSize - 1;
            for (let i = left; i <= leftEnd; i++) {
                this.arr[i] += val;
            }
            
            // Full blocks - use lazy propagation
            for (let b = leftBlock + 1; b < rightBlock; b++) {
                this.lazy[b] += val;
            }
            
            // Right partial block
            const rightStart = rightBlock * this.blockSize;
            for (let i = rightStart; i <= right; i++) {
                this.arr[i] += val;
            }
        }
    }
    
    // Get value at index
    get(idx) {
        const blockIdx = Math.floor(idx / this.blockSize);
        return this.arr[idx] + this.lazy[blockIdx];
    }
    
    // Query sum in range
    rangeSum(left, right) {
        let sum = 0;
        for (let i = left; i <= right; i++) {
            sum += this.get(i);
        }
        return sum;
    }
}

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const raq = new RangeAddQuery(arr);
raq.rangeAdd(2, 6, 10); // Add 10 to indices 2-6
console.log(raq.get(4)); // 15 (was 5)
console.log(raq.rangeSum(0, 8)); // Sum after update

Example: Mo's Algorithm with modifications

// Mo's Algorithm pattern with custom comparator
function mosWithCustomSort(arr, queries, blockSize = null) {
    const n = arr.length;
    const size = blockSize || Math.floor(Math.sqrt(n));
    
    // Create indexed queries
    const indexedQueries = queries.map((q, idx) => ({
        left: q[0],
        right: q[1],
        idx: idx,
        block: Math.floor(q[0] / size)
    }));
    
    // Hilbert curve ordering for better cache performance
    indexedQueries.sort((a, b) => {
        if (a.block !== b.block) {
            return a.block - b.block;
        }
        // Alternate direction based on block parity
        return a.block % 2 === 0 ? 
            a.right - b.right : 
            b.right - a.right;
    });
    
    return indexedQueries;
}

// Benefits of alternating direction:
// - Reduces pointer movement between queries
// - Better cache locality
// - Can reduce total operations by ~25%

console.log("Block size optimization:");
console.log("For n = 10000, optimal block size ≈", 
    Math.floor(Math.sqrt(10000))); // 100
console.log("Expected operations per query:", 
    Math.sqrt(10000) + Math.sqrt(10000)); // ~200

Warning: Square root decomposition has limitations:

Not optimal: O(√n) is slower than O(log n) segment trees for large n
Fixed block size: Once chosen, changing block size requires rebuilding
Mo's requires offline: Cannot handle online queries
Memory access: Can have poor cache performance for very large arrays

Summary: Square Root Decomposition Pattern

Core Idea: Divide array into √n blocks of size √n each, precompute values for each block
Block Size Choice: √n provides optimal balance - fewer blocks = larger partials, more blocks = more block storage
Range Queries: Process O(√n) full blocks + O(√n) partial elements at boundaries = O(√n) total
Point Updates: Update element O(1) + update block value O(1) or O(√n) depending on operation
Mo's Algorithm: Offline query optimization - sort queries by (left/√n, right), process in order with O((n+q)√n) total
Query Ordering: Hilbert curve or alternating direction improves cache performance
Lazy Propagation: Mark blocks with pending updates, apply when queried - defers expensive operations
Trade-offs: Simpler than segment trees but slower; better than brute force; good middle ground
Applications: Range sum/min/max/GCD queries, distinct counts, frequency queries, problem-specific operations
When to Use: Need range queries + updates, segment tree too complex, O(√n) performance acceptable (n ≤ 10^5)

Related Cheatsheets

Datastructures-algorithms