原题链接

题意简述

给出 $n$ 头奶牛，每头可分为三种，对于 $q$ 次询问，给出区间内各种奶牛的数量。

思路

题目的数据范围限制为 $N,Q\leq10^5$ ，肯定不能够使用暴力对于每一个区间跑一遍统计。这一题有只要求查询而不要求修改，很自然就想到了前缀和。

前缀和

那么什么是前缀和呢？

根据OI Wiki 上的解释

前缀和是一种重要的预处理，能大大降低查询的时间复杂度。我们可以简单理解为“数列的前 $n$ 项的和”。

如果用数组 $a$ 和其前缀和数组 $b$ 表示出来

$a_1=1,a_2=5,a_3=3,a_4=2,…$

则数组 $b$

$b_1=1,b_2=6,b_3=9,b_4=11,…$

不难推出式子

$$b_i=b_{i-1}+a_i$$

如果要查询数组 $a$ 从 $l$ 到 $r$ 之间所有数的和，只用输出 $br-b{l-1}$​ ,

原理：

$$b_r=\sum_{i=1}^{r}a_i$$ $$b_{l-1}=\sum_{i=1}^{l-1}a_i$$

注意，一定是 $l-1$ 如果是 $l$ 就会将 $a_l$ 减去

根据上述，给出代码如下

代码

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    char ch = getchar();
    int ret = 0, f = 1;
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -f;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        ret = (ret << 1) + (ret << 3) + ch - '0';
        ch = getchar();
    }
    return ret * f;
}
const int N = 100005;
int n, q, a[2][N], b[2][N], c[2][N];
// a[0],b[0],c[0]为原始数组
// a[1],b[1],c[1]为对应的前缀和数组
int main() {
    n = read();
    q = read();
    for (int i = 1; i <= n; i++) {
        int t = read();
        if (t == 1)
            a[0][i]++;
        else if (t == 2)
            b[0][i]++;
        else if (t == 3)
            c[0][i]++;
        a[1][i] = a[1][i - 1] + a[0][i];
        b[1][i] = b[1][i - 1] + b[0][i];
        c[1][i] = c[1][i - 1] + c[0][i];
    }
    for (int i = 1; i <= q; i++) {
        int l = read(), r = read();
        printf("%d %d %d\n", a[1][r] - a[1][l - 1], b[1][r] - b[1][l - 1], c[1][r] - c[1][l - 1]);
    }
}

后记

前缀和的应用并不只上述这么简单，许多看似基础的算法也是如此，往往可以通过一些有趣的改进拓展到更多地方。