前缀和是一个十分实用的技巧，难度很低，机试中很常见，要求同学们必须掌握。

前缀和的应用十分的多，很多时候和差分思想结合起来能无往不利。

下面列举几个机试中常见的考察方法

1、给你n个整数，然后进行m次询问，其中n和m很大，每次询问让你求某段区间的和。
解析：由于n和m很大，所以不能在每次询问的时候暴力遍历这段区间的和。那么我们考虑用前缀和进行预处理，sum[i]表示前i个数的前缀和，对于每次询问的区间[l, r]的结果为sum[r] - sum[l-1]。

2、见下面例题

TAT的个数
题目描述：
小诺有一个只包含T和A的字符串，小诺想知道这个序列中有多少个TAT？

比如:TATT中包含了2个不同位置的TAT，TAATT中包含了4个不同位置的TAT。
输入描述：
多组数据输入。
输入一行字符串，字符串长度小于100000。
输出描述：
输出答案。
输入样例#:
TATT
输出样例#:
2
题目来源：
DreamJudge 1646

题目解析：我们只需要枚举字符串中的每个A，如果我们知道每一个A它前面有多少个T记为left，它后面有多少个T记为right，那么经过这个A的TAT数量就是left*right。然后我们用前缀和的思想预处理出每个位置的left和right即可直接枚举A求解。

参考代码

#include <stdio.h>  
#include <string.h>  
  
typedef long long ll;  
ll left[100005];//从左边开始到第i个有多少个T  
ll right[100005];//从右边开始到第i个有多少个T  
char s[100005];  
int main() {  
    while (scanf("%s", s+1) != EOF) {  
        int len = strlen(s+1);  
        for (int i = 1; i <= len; i++) {  
            if (s[i] == 'T') left[i] = left[i - 1] + 1;  
            else left[i] = left[i - 1];  
        }  
        for (int i = len; i >= 1; i--) {  
            if (s[i] == 'T') right[i] = right[i + 1] + 1;  
            else right[i] = right[i + 1];  
        }  
        ll sum = 0;  
        for...

掌握前缀和技巧