分块算法

分块算法是一种重要的优化策略，通过将数据分成若干个小块，在每个块上进行特定的预处理，可以大大提高算法的效率。本文将介绍分块算法的基本思想、常见应用场景和实现技巧。

基本思想

分块算法的核心思想是将长度为n的数据序列分成大小为sqrt(n)的连续块，然后对每个块进行单独的维护。这样，对于涉及范围操作的问题，我们可以：

1. 对于完全包含在某个块内的查询/修改操作，直接在块内处理
2. 对于跨越多个块的操作，将其分解为"完整块"和"块内零散部分"两种情况处理

这种数据结构设计在时间复杂度和空间复杂度之间取得了良好的平衡，通常可以达到O(sqrt(n))的查询和修改复杂度。

数组分块

基本结构

对于一个长度为n的数组，我们将其分为sqrt(n)个块，每个块包含sqrt(n)个元素。

const int MAXN = 100005;
const int BLOCK_SIZE = 320;  // 大约是sqrt(MAXN)

int n;                  // 数组长度
int arr[MAXN];         // 原始数组
int block[BLOCK_SIZE]; // 块的信息（如和、最大值等）
int block_size;        // 每个块的大小
int num_blocks;        // 块的数量

// 初始化分块
void init() {
    block_size = sqrt(n);  // 确定每个块的大小
    num_blocks = (n + block_size - 1) / block_size;  // 向上取整得到块数

    // 初始化每个块的信息
    memset(block, 0, sizeof(block));
    for (int i = 0; i < n; i++) {
        block[i / block_size] += arr[i];  // 计算每个块的和
    }
}

区间查询

以区间和查询为例：

// 查询区间[l, r]的和
int query(int l, int r) {
    int sum = 0;
    int start_block = l / block_size;
    int end_block = r / block_size;

    if (start_block == end_block) {
        // 如果查询的区间在同一个块内
        for (int i = l; i <= r; i++) {
            sum += arr[i];
        }
    } else {
        // 处理第一个块的右边部分
        for (int i = l; i < (start_block + 1) * block_size; i++) {
            sum += arr[i];
        }

        // 处理完整的中间块
        for (int i = start_block + 1; i < end_block; i++) {
            sum += block[i];
        }

        // 处理最后一个块的左边部分
        for (int i = end_block * block_size; i <= r; i++) {
            sum += arr[i];
        }
    }

    return sum;
}

单点修改

// 将位置pos的值修改为val
void update(int pos, int val) {
    int delta = val - arr[pos];
    arr[pos] = val;  // 更新原数组
    block[pos / block_size] += delta;  // 更新对应的块
}

区间修改与懒标记

如果需要支持区间修改，我们可以结合懒标记技术：

int lazy[BLOCK_SIZE];  // 懒标记数组，记录每个块的待更新值

// 对区间[l, r]的所有元素加上val
void rangeAdd(int l, int r, int val) {
    int start_block = l / block_size;
    int end_block = r / block_size;

    if (start_block == end_block) {
        // 如果修改区间在同一个块内
        for (int i = l; i <= r; i++) {
            arr[i] += val;
            block[start_block] += val;  // 更新块的和
        }
    } else {
        // 处理第一个块的右边部分
        for (int i = l; i < (start_block + 1) * block_size; i++) {
            arr[i] += val;
            block[start_block] += val;
        }

        // 对于完整的中间块，使用懒标记
        for (int i = start_block + 1; i < end_block; i++) {
            lazy[i] += val;
            block[i] += val * block_size;  // 更新块的和
        }

        // 处理最后一个块的左边部分
        for (int i = end_block * block_size; i <= r; i++) {
            arr[i] += val;
            block[end_block] += val;
        }
    }
}

// 查询时需要考虑懒标记
int queryWithLazy(int l, int r) {
    int sum = 0;
    int start_block = l / block_size;
    int end_block = r / block_size;

    if (start_block == end_block) {
        // 如果查询区间在同一个块内
        for (int i = l; i <= r; i++) {
            sum += arr[i] + lazy[start_block];  // 加上懒标记值
        }
    } else {
        // 处理第一个块的右边部分
        for (int i = l; i < (start_block + 1) * block_size; i++) {
            sum += arr[i] + lazy[start_block];
        }

        // 处理完整的中间块
        for (int i = start_block + 1; i < end_block; i++) {
            sum += block[i];  // 块的和已经在rangeAdd中更新过了
        }

        // 处理最后一个块的左边部分
        for (int i = end_block * block_size; i <= r; i++) {
            sum += arr[i] + lazy[end_block];
        }
    }

    return sum;
}

根号分治

分块算法的一个变种是根号分治，它将查询分为根号个批次处理，每批次包含根号个查询。

以莫队算法为例，莫队算法是一种离线查询算法，用于处理区间查询问题：

struct Query {
    int l, r, idx;  // 查询区间的左右端点和查询的原始编号

    // 按块的编号和右端点排序
    bool operator<(const Query& other) const {
        int block_l = l / block_size;
        int block_other = other.l / block_size;
        if (block_l != block_other)
            return block_l < block_other;
        return r < other.r;
    }
};

// 使用莫队算法处理区间查询
void processMoQueries(int arr[], int n, Query queries[], int q) {
    block_size = sqrt(n);
    sort(queries, queries + q);  // 按照分块排序查询

    int answers[q];
    int currentL = 0, currentR = -1;
    int currentResult = 0;

    // 移动指针的辅助函数
    auto add = [&](int pos) {
        // 将位置pos的元素加入当前结果
        // 具体实现取决于问题
    };

    auto remove = [&](int pos) {
        // 将位置pos的元素从当前结果中移除
        // 具体实现取决于问题
    };

    for (int i = 0; i < q; i++) {
        Query& query = queries[i];

        // 调整当前的查询区间
        while (currentL > query.l) {
            currentL--;
            add(currentL);
        }
        while (currentR < query.r) {
            currentR++;
            add(currentR);
        }
        while (currentL < query.l) {
            remove(currentL);
            currentL++;
        }
        while (currentR > query.r) {
            remove(currentR);
            currentR--;
        }

        // 保存当前查询的结果
        answers[query.idx] = currentResult;
    }

    // 按原始顺序输出结果
    for (int i = 0; i < q; i++) {
        cout << answers[i] << endl;
    }
}

分块排序

对于需要频繁区间询问和单点修改的问题，我们可以对每个块单独排序：

int arr[MAXN];            // 原始数组
int sorted[MAXN];         // 排序后的数组副本
int block_id[MAXN];       // 每个元素所属的块编号

// 初始化并对每个块排序
void initAndSort() {
    block_size = sqrt(n);
    num_blocks = (n + block_size - 1) / block_size;

    for (int i = 0; i < n; i++) {
        block_id[i] = i / block_size;
        sorted[i] = arr[i];
    }

    // 对每个块单独排序
    for (int i = 0; i < num_blocks; i++) {
        int left = i * block_size;
        int right = min((i + 1) * block_size - 1, n - 1);
        sort(sorted + left, sorted + right + 1);
    }
}

// 单点修改后重新排序对应的块
void update(int pos, int val) {
    arr[pos] = val;
    int bID = block_id[pos];
    int left = bID * block_size;
    int right = min((bID + 1) * block_size - 1, n - 1);

    // 重新拷贝并排序该块
    for (int i = left; i <= right; i++) {
        sorted[i] = arr[i];
    }
    sort(sorted + left, sorted + right + 1);
}

// 查询区间[l,r]中小于等于val的元素个数
int countLessEqual(int l, int r, int val) {
    int result = 0;
    int start_block = l / block_size;
    int end_block = r / block_size;

    if (start_block == end_block) {
        // 如果在同一个块内，直接暴力统计
        for (int i = l; i <= r; i++) {
            if (arr[i] <= val) result++;
        }
    } else {
        // 处理第一个块的部分元素
        for (int i = l; i < (start_block + 1) * block_size; i++) {
            if (arr[i] <= val) result++;
        }

        // 处理完整的中间块（利用排序后的数组二分查找）
        for (int i = start_block + 1; i < end_block; i++) {
            int left = i * block_size;
            int right = (i + 1) * block_size - 1;
            result += upper_bound(sorted + left, sorted + right + 1, val) - (sorted + left);
        }

        // 处理最后一个块的部分元素
        for (int i = end_block * block_size; i <= r; i++) {
            if (arr[i] <= val) result++;
        }
    }

    return result;
}

分块应用：区间众数查询

使用分块算法处理区间众数查询问题：

const int MAXN = 100005;
int arr[MAXN], n;
int block_size, num_blocks;
unordered_map<int, int> freq;  // 用于统计频率

// 处理区间[l, r]的众数查询
pair<int, int> queryMostFrequent(int l, int r) {
    freq.clear();
    int max_freq = 0, mode = -1;

    int start_block = l / block_size;
    int end_block = r / block_size;

    if (start_block == end_block) {
        // 如果在同一个块内，直接暴力统计
        for (int i = l; i <= r; i++) {
            freq[arr[i]]++;
            if (freq[arr[i]] > max_freq || (freq[arr[i]] == max_freq && arr[i] < mode)) {
                max_freq = freq[arr[i]];
                mode = arr[i];
            }
        }
    } else {
        // 处理第一个块的部分元素
        for (int i = l; i < (start_block + 1) * block_size; i++) {
            freq[arr[i]]++;
        }

        // 处理完整的中间块（可以预处理每个块的频率信息）
        for (int i = start_block + 1; i < end_block; i++) {
            for (int j = i * block_size; j < (i + 1) * block_size && j < n; j++) {
                freq[arr[j]]++;
            }
        }

        // 处理最后一个块的部分元素
        for (int i = end_block * block_size; i <= r; i++) {
            freq[arr[i]]++;
        }

        // 找出最高频率的元素
        for (auto& p : freq) {
            if (p.second > max_freq || (p.second == max_freq && p.first < mode)) {
                max_freq = p.second;
                mode = p.first;
            }
        }
    }

    return {mode, max_freq};
}

块状链表

块状链表是分块思想的另一种实现，每个节点包含一个子链表，适合处理频繁插入删除的问题：

struct BlockNode {
    vector<int> data;       // 块中存储的数据
    BlockNode* next;        // 指向下一个块

    BlockNode() : next(nullptr) {}
};

class BlockList {
private:
    BlockNode* head;
    int block_size;
    int size;

public:
    BlockList(int n) {
        head = nullptr;
        block_size = sqrt(n);
        size = 0;
    }

    // 在位置pos插入值val
    void insert(int pos, int val) {
        if (pos > size) {
            pos = size;  // 如果位置超出当前大小，则在末尾插入
        }

        // 找到要插入的块和在块中的位置
        BlockNode* current = head;
        BlockNode* prev = nullptr;
        int count = 0;

        while (current && count + current->data.size() < pos) {
            count += current->data.size();
            prev = current;
            current = current->next;
        }

        if (!current) {
            // 如果需要在末尾创建新块
            current = new BlockNode();
            if (prev) {
                prev->next = current;
            } else {
                head = current;
            }
        }

        // 在块中的位置
        int block_pos = pos - count;
        current->data.insert(current->data.begin() + block_pos, val);
        size++;

        // 如果一个块太大，则分裂
        if (current->data.size() > 2 * block_size) {
            BlockNode* new_node = new BlockNode();
            int half = current->data.size() / 2;

            // 移动后半部分到新块
            new_node->data.assign(current->data.begin() + half, current->data.end());
            current->data.resize(half);

            // 将新块插入链表
            new_node->next = current->next;
            current->next = new_node;
        }
    }

    // 删除位置pos的元素
    void remove(int pos) {
        if (pos >= size) return;

        // 找到要删除的块和在块中的位置
        BlockNode* current = head;
        BlockNode* prev = nullptr;
        int count = 0;

        while (current && count + current->data.size() <= pos) {
            count += current->data.size();
            prev = current;
            current = current->next;
        }

        if (!current) return;  // 超出范围

        // 在块中的位置
        int block_pos = pos - count;
        current->data.erase(current->data.begin() + block_pos);
        size--;

        // 如果块太小，则合并或重分布
        if (current->data.empty()) {
            if (prev) {
                prev->next = current->next;
            } else {
                head = current->next;
            }
            delete current;
        } else if (current->data.size() < block_size/2 && current->next) {
            // 尝试与下一个块合并
            if (current->data.size() + current->next->data.size() <= block_size) {
                current->data.insert(current->data.end(), current->next->data.begin(), current->next->data.end());
                BlockNode* temp = current->next;
                current->next = temp->next;
                delete temp;
            }
        }
    }

    // 获取位置pos的元素
    int get(int pos) {
        if (pos >= size) return -1;  // 超出范围

        BlockNode* current = head;
        int count = 0;

        while (current && count + current->data.size() <= pos) {
            count += current->data.size();
            current = current->next;
        }

        if (!current) return -1;  // 超出范围

        return current->data[pos - count];
    }
};

分块技巧与优化

1. 块大小的选择：通常sqrt(n)是个好的选择，但在实际问题中可能需要根据问题特性和数据规模微调。

2. 预处理与缓存：对每个块预先计算常用统计信息，如和、最大值、最小值等。

3. 延迟重构：对于频繁更新的情况，可以使用懒标记延迟块内元素的实际更新。

4. 分块排序：对每个块单独排序，可以提高区间查询的效率。

5. 自适应分块：根据操作频率动态调整块的大小或结构。

复杂度分析

对于长度为n的数组，将其分为大小为sqrt(n)的块：

• 空间复杂度：O(n)
• 单点修改时间复杂度：O(1)
• 区间查询时间复杂度：O(sqrt(n))
• 区间修改时间复杂度：O(sqrt(n))

练习题目推荐

1. POJ 2104: K-th Number (分块排序应用)
2. SPOJ DQUERY: D-Query (莫队算法)
3. Codeforces 617E: XOR and Favorite Number (分块查询)
4. SPOJ GIVEAWAY: Give Away (分块排序/树状数组)
5. Codeforces 940F: Machine Learning (带修改的莫队算法)

总结

分块算法是一种强大的优化策略，特别适合处理区间查询和修改的问题。它通过将数据分成固定大小的块，在时间和空间复杂度之间取得良好的平衡。相比于线段树、树状数组等高级数据结构，分块算法实现简单，思想直观，维护成本低，而且在某些特定问题上更加灵活。掌握分块算法及其变种，可以帮助解决许多复杂的算法问题。