Ant In Loop

Sqrt Decomposition

Introduction

Sqrt Decomposition is a technique that divides data into √n blocks to achieve O(√n) time complexity for range queries and updates, balancing between naive O(n) and complex O(log n) solutions.

Key Concepts

• Divide array into √n blocks (each of size √n)
• Precompute block-level information
• For queries: Combine results from complete blocks and partial elements

Mathematics Behind Sqrt Decomposition

The algorithm is based on the inequality:

√n × √n ≥ n

This ensures:

• Number of blocks: O(√n)
• Elements per block: O(√n)
• Total operations per query: O(√n)

Optimal Block Size: For array of size n, optimal block size is k = √n, minimizing the sum of:

• O(n/k) block operations
• O(k) element operations

Time and Space Complexity

• Preprocessing: O(n)
• Range Query: O(√n)
• Point Update: O(1)
• Range Update: O(√n)
• Space: O(n)

Problem Examples

Easy Problems

1. Range Sum Queries (Codeforces 633B)

Given an array, answer range sum queries and support point updates.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<int> arr, block_sum;
int block_size;

void build(int n) {
    block_size = sqrt(n);
    block_sum.resize((n + block_size - 1) / block_size, 0);
    
    for (int i = 0; i < n; i++)
        block_sum[i / block_size] += arr[i];
}

void update(int idx, int val) {
    int block_idx = idx / block_size;
    block_sum[block_idx] += val - arr[idx];
    arr[idx] = val;
}

int query(int l, int r) {
    int sum = 0;
    while (l <= r && l % block_size != 0) {
        sum += arr[l];
        l++;
    }
    while (l + block_size <= r) {
        sum += block_sum[l / block_size];
        l += block_size;
    }
    while (l <= r) {
        sum += arr[l];
        l++;
    }
    return sum;
}

int main() {
    int n = 8;
    arr = {1, 3, 5, 7, 9, 11, 13, 15};
    build(n);
    
    cout << query(1, 5) << endl; // 3+5+7+9+11 = 35
    update(3, 10);
    cout << query(1, 5) << endl; // 3+5+10+9+11 = 38
    
    return 0;
}

Input/Output Example

Input: (built into code)
Array: [1, 3, 5, 7, 9, 11, 13, 15]

Output:
35
38

2. Range Minimum Queries (Codeforces 514B)

Find minimum in range with point updates.

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;

vector<int> arr, block_min;
int block_size;

void build(int n) {
    block_size = sqrt(n);
    block_min.resize((n + block_size - 1) / block_size, INT_MAX);
    
    for (int i = 0; i < n; i++)
        block_min[i / block_size] = min(block_min[i / block_size], arr[i]);
}

void update(int idx, int val) {
    int block_idx = idx / block_size;
    arr[idx] = val;
    int start = block_idx * block_size;
    int end = min(start + block_size, (int)arr.size());
    block_min[block_idx] = INT_MAX;
    for (int i = start; i < end; i++)
        block_min[block_idx] = min(block_min[block_idx], arr[i]);
}

int query(int l, int r) {
    int mn = INT_MAX;
    while (l <= r && l % block_size != 0) {
        mn = min(mn, arr[l]);
        l++;
    }
    while (l + block_size <= r) {
        mn = min(mn, block_min[l / block_size]);
        l += block_size;
    }
    while (l <= r) {
        mn = min(mn, arr[l]);
        l++;
    }
    return mn;
}

int main() {
    int n = 8;
    arr = {5, 3, 8, 1, 7, 4, 2, 6};
    build(n);
    
    cout << query(1, 5) << endl; // min(3,8,1,7,4) = 1
    update(3, 10);
    cout << query(1, 5) << endl; // min(3,8,10,7,4) = 3
    
    return 0;
}

Intermediate Problems

1. Range Sum with Range Update (Codeforces 52C)

Support range addition and range sum queries.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<long long> arr, block_sum, block_add;
int block_size;

void build(int n) {
    block_size = sqrt(n);
    block_sum.resize((n + block_size - 1) / block_size, 0);
    block_add.resize((n + block_size - 1) / block_size, 0);
    
    for (int i = 0; i < n; i++)
        block_sum[i / block_size] += arr[i];
}

void range_update(int l, int r, int val) {
    while (l <= r && l % block_size != 0) {
        arr[l] += val;
        block_sum[l / block_size] += val;
        l++;
    }
    while (l + block_size <= r) {
        block_add[l / block_size] += val;
        block_sum[l / block_size] += val * block_size;
        l += block_size;
    }
    while (l <= r) {
        arr[l] += val;
        block_sum[l / block_size] += val;
        l++;
    }
}

long long range_query(int l, int r) {
    long long sum = 0;
    while (l <= r && l % block_size != 0) {
        sum += arr[l] + block_add[l / block_size];
        l++;
    }
    while (l + block_size <= r) {
        sum += block_sum[l / block_size];
        l += block_size;
    }
    while (l <= r) {
        sum += arr[l] + block_add[l / block_size];
        l++;
    }
    return sum;
}

int main() {
    int n = 8;
    arr = {1, 3, 5, 7, 9, 11, 13, 15};
    build(n);
    
    cout << range_query(1, 5) << endl; // 3+5+7+9+11 = 35
    range_update(2, 6, 2);
    cout << range_query(1, 5) << endl; // 3+7+9+11+13 = 43
    
    return 0;
}

2. Mo's Algorithm (Codeforces 86D)

Count distinct elements in range queries (offline processing).

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

struct Query {
    int l, r, idx;
};

vector<int> arr, cnt, ans;
vector<Query> queries;
int curr_ans = 0;

void add(int x) {
    if (cnt[x] == 0) curr_ans++;
    cnt[x]++;
}

void remove(int x) {
    cnt[x]--;
    if (cnt[x] == 0) curr_ans--;
}

int main() {
    int n = 8, q = 3;
    arr = {1, 2, 3, 1, 1, 2, 1, 2};
    cnt.resize(4, 0);
    queries = {{0, 4, 0}, {1, 6, 1}, {2, 7, 2}};
    ans.resize(q);
    
    int block_size = sqrt(n);
    sort(queries.begin(), queries.end(), [&](Query a, Query b) {
        if (a.l / block_size != b.l / block_size)
            return a.l < b.l;
        return (a.l / block_size % 2) ? a.r > b.r : a.r < b.r;
    });
    
    int l = 0, r = -1;
    for (Query q : queries) {
        while (l > q.l) add(arr[--l]);
        while (r < q.r) add(arr[++r]);
        while (l < q.l) remove(arr[l++]);
        while (r > q.r) remove(arr[r--]);
        ans[q.idx] = curr_ans;
    }
    
    for (int x : ans) cout << x << " "; // 3 3 2
    return 0;
}

Hard Problem

1. Online Range Mode Query (Codeforces 840D)

Find the most frequent element in a range that appears more than threshold times.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
#include <algorithm>
using namespace std;

vector<int> arr;
vector<vector<pair<int, int>>> block_mode;
vector<unordered_map<int, int>> block_freq;
int block_size;

void build(int n) {
    block_size = sqrt(n);
    int blocks = (n + block_size - 1) / block_size;
    block_mode.resize(blocks);
    block_freq.resize(blocks);
    
    for (int b = 0; b < blocks; b++) {
        int start = b * block_size;
        int end = min(start + block_size, n);
        unordered_map<int, int> freq;
        vector<pair<int, int>> mode;
        
        for (int i = start; i < end; i++) {
            freq[arr[i]]++;
            mode.emplace_back(freq[arr[i]], arr[i]);
        }
        sort(mode.rbegin(), mode.rend());
        block_mode[b] = mode;
        block_freq[b] = freq;
    }
}

int query(int l, int r, int threshold) {
    unordered_map<int, int> freq;
    int res = -1;
    
    while (l <= r && l % block_size != 0) {
        freq[arr[l]]++;
        if (freq[arr[l]] > threshold && (res == -1 || arr[l] < res))
            res = arr[l];
        l++;
    }
    while (l + block_size <= r) {
        int b = l / block_size;
        for (auto [cnt, val] : block_mode[b]) {
            if (cnt + freq[val] > threshold) {
                if (res == -1 || val < res) res = val;
            } else break;
        }
        for (auto [val, cnt] : block_freq[b]) {
            freq[val] += cnt;
        }
        l += block_size;
    }
    while (l <= r) {
        freq[arr[l]]++;
        if (freq[arr[l]] > threshold && (res == -1 || arr[l] < res))
            res = arr[l];
        l++;
    }
    return res;
}

int main() {
    int n = 10, q = 2;
    arr = {1, 2, 3, 1, 2, 1, 1, 3, 2, 1};
    build(n);
    
    cout << query(1, 7, 2) << endl; // 1 (appears 4 times)
    cout << query(0, 9, 3) << endl; // 1 (appears 5 times)
    
    return 0;
}