子数组可整除元素计数的高效查询与更新方案求解

问题背景 #

给定大小为 (N)（(1 ≤ N ≤ 2×10^5)）的正整数数组（元素不超过 (10^5)），需支持 (Q) 次（(1 ≤ Q ≤ 10^5)）操作：

1. 整除计数查询（Q）：统计子数组 ([left, right]) 中能被指定数值整除的元素数量。
2. 点更新（U）：修改数组指定索引的元素值。

暴力解法（(O(NQ)) 时间复杂度）会因数据规模过大超时，需优化。

示例输入：

6 4
6 5 4 3 2 1
Q 0 3 1
Q 1 4 2
U 3 8
Q 1 5 2

示例输出：

4
2
3

暴力超时代码：

#include <iostream>
#include <vector>

int main() {
    using std::cin, std::cout;

    int N, Q;
    cin >> N >> Q;

    std::vector<int> array(N);
    for (int &i : array) cin >> i;

    for (int q = 0; q < Q; q++) {
        char t;
        cin >> t;
        if (t == 'Q') {
            int left, right, num;
            cin >> left >> right >> num;
            int cnt = 0;
            for (int i = left; i <= right; i++) {
                if (array[i] % num == 0) cnt++;
            }
            cout << cnt << '\n';
        } else {
            int index, newNum;
            cin >> index >> newNum;
            array[index] = newNum;
        }
    }
    return 0;
}

优化方案：根号分解分块策略 #

利用元素最大值不超过 (10^5) 的特性，采用根号分解平衡查询与更新的时间效率，核心是将除数分为「小除数」和「大除数」两类处理：

核心思路 #

设定阈值 (K = \sqrt{10^5} ≈ 317)，块大小 (B = \sqrt{N} ≈ 450)：

• 小除数（(d ≤ K)）：预先维护每个块中能被 (d) 整除的元素数量，查询时直接累加完整块的统计值，更新时同步维护这些统计数据。
• 大除数（(d > K)）：由于 (d) 较大，每个块中能被 (d) 整除的元素数量极少（最多 (B/d ≈ 1) 个），查询时直接遍历完整块内元素统计即可，无需预先维护。

实现步骤 #

1. 分块预处理

   • 将数组划分为大小为 (B) 的块，维护二维数组 block_cnt[bid][d]，记录第 bid 块中能被 (d)（(d ≤ K)）整除的元素数。
   • 保留原数组用于处理零散元素和大除数查询。

2. 更新操作

   • 找到待更新元素所在块，遍历所有 (d ≤ K)：若旧值能被 (d) 整除则块统计减1，若新值能被 (d) 整除则块统计加1，最后更新原数组值。

3. 查询操作

   • 遍历区间两端的不完整块，暴力统计符合条件的元素。
   • 中间完整块：若为小除数则直接累加块统计值；若为大除数则遍历块内元素统计。

复杂度分析 #

• 预处理：(O(NK))，(2e5317 ≈ 6e7)，可接受。
• 更新：(O(K))，单次更新遍历317个小除数，总 (1e5*317 ≈3e7)，可接受。
• 查询：(O(\sqrt{N}))，无论小/大除数，单次查询时间均为根号级别。
• 总时间复杂度：(O((N+Q)*\sqrt{M}))（(M=1e5)），完全满足时限要求。

优化后代码 #

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

const int MAX_N = 2e5 + 10;
const int K = 317;          // sqrt(1e5) 取整
const int BLOCK_SIZE = 450; // sqrt(2e5) 取整

int arr[MAX_N];
int block_cnt[500][K + 1]; // 块数最多约445，预留冗余空间

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    // 初始化块统计
    for (int i = 0; i < N; ++i) {
        cin >> arr[i];
        int bid = i / BLOCK_SIZE;
        for (int d = 1; d <= K; ++d) {
            if (arr[i] % d == 0) {
                block_cnt[bid][d]++;
            }
        }
    }

    while (Q--) {
        char op;
        cin >> op;
        if (op == 'U') {
            int idx, new_val;
            cin >> idx >> new_val;
            int old_val = arr[idx];
            int bid = idx / BLOCK_SIZE;

            // 更新小除数的块统计
            for (int d = 1; d <= K; ++d) {
                if (old_val % d == 0) block_cnt[bid][d]--;
                if (new_val % d == 0) block_cnt[bid][d]++;
            }
            arr[idx] = new_val;
        } else if (op == 'Q') {
            int L, R, d;
            cin >> L >> R >> d;
            int res = 0;
            int start_bid = L / BLOCK_SIZE;
            int end_bid = R / BLOCK_SIZE;

            // 区间在同一块内，直接暴力
            if (start_bid == end_bid) {
                for (int i = L; i <= R; ++i) {
                    if (arr[i] % d == 0) res++;
                }
                cout << res << '\n';
                continue;
            }

            // 处理左右不完整块
            for (int i = L; i < (start_bid + 1) * BLOCK_SIZE; ++i) {
                if (arr[i] % d == 0) res++;
            }
            for (int i = end_bid * BLOCK_SIZE; i <= R; ++i) {
                if (arr[i] % d == 0) res++;
            }

            // 处理中间完整块
            if (d <= K) {
                for (int bid = start_bid + 1; bid < end_bid; ++bid) {
                    res += block_cnt[bid][d];
                }
            } else {
                for (int bid = start_bid + 1; bid < end_bid; ++bid) {
                    int block_start = bid * BLOCK_SIZE;
                    int block_end = block_start + BLOCK_SIZE;
                    for (int i = block_start; i < block_end; ++i) {
                        if (arr[i] % d == 0) res++;
                    }
                }
            }

            cout << res << '\n';
        }
    }

    return 0;
}

其他可选方案 #

• 带修Mo算法：若支持离线处理所有查询，可使用带修Mo算法，时间复杂度 (O((N+Q)\sqrt{N}))，但实现复杂度较高。
• 因子前缀和数组：对每个除数维护前缀和数组，仅适用于无更新场景，更新时会因需遍历大量倍数导致超时。

内容的提问来源于stack exchange，提问作者user25680598