啊，哈喽，小伙伴们大家好。我是#Y清墨，今天呐，我要介绍的是前缀和入门。
导语
我们先来思考一个问题：小帅有n个编号为1~n的帐号，每个帐号里装有ci个文章，求从a至b的帐号里的文章数量和。
一.前缀和
（1）解题一
没学前缀和的小伙伴肯定会这样打。
#include<bits/stdc++.h>
using namespace std;
int n,a,b,c[101],ans=0,i;
int main(){cin>>n>>a>>b;for(i=1;i<=n;i++){cin>>c[i];if(i>=a&&i<=b)ans += c[i];}cout<<ans;return 0;
}这种算法要得出一个区间之和，这题只需要取一次区间值，时间复杂度需要 O(n)，但是呢，啊，如果 2 次，4 次，1000 次，数据再一大，暴力算法1000%会超时的，这时，前缀和的优势就体现出来了因为它会取区间之和只需要 O(1)。
（2）前缀和详讲
讲解之前呢，先讲一下前缀和。
概念：前缀和就是数组的前 i 项之和。
很明显，能画一个表格。
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 |
| a数组 | 1 | 1 | 2 | 3 | 5 | 8 |
| b数组 | 1 | 2 | 4 | 7 | 12 | 20 |
啊结合for循环那也是简简单单，易如反掌。
for(i=1;i<=n;i++)
{cin>>a[i];b[i]=b[i-1]+a[i];
}二.前缀和题目
（1）所有奇数长度子数组的和
题目描述
给你一个正整数数组 a ，请你计算所有可能的奇数长度子数组的和。
子数组的定义为：原数组中的一个连续子序列。
请你输出数组 a 中所有奇数长度子数组的和。
输入格式
第 1 行：1 个正整数 N，不超过 10000 。
第 2 行：N 个整数，范围 [1,10000] 。
输出格式
输出一个整数。
样例
输入数据 1
5
1 4 2 5 3
输出数据 1
58
样例解释
所有奇数长度子数组和它们的和为：
[1] = 1，[4] = 4，[2] = 2，[5] = 5，[3] = 3，[1,4,2] = 7，[4,2,5] = 11，[2,5,3] = 10
，[1,4,2,5,3] = 15，我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58。
#include<bits/stdc++.h>
using namespace std;
long long n,a[10001];
int main(){scanf("%lld",&n);for(int i=1;i<=n;i++){int x;scanf("%lld",&x);a[i]=a[i-1]+x;}long long cnt=0;for(int i=1;i<=n;i=i+2)//i+2是因为是奇数长度{for(int j=1;j<=n-i+1;j++){int r=j+i-1;//指针cnt+=a[r]-a[j-1];}}cout<<cnt;return 0;
}（2）有多少个数字1
题目描述
小明很喜欢喜欢数字 1 ，他想研究两个整数之间所有整数出现了多少个数字 1 。
现在他想求 n 次，a 和 b 之间（包含 a 和 b ）的所有整数的 1 出现的次数，聪明的你能够帮帮小明吗？
输入格式
第 1 行 1 个整数 n ( 1 <= n <= 1000000 )。
下面有 n 行，每行 2 个整数 a 和 b ( 1 <= a , b <= 1000000 )。
输出格式
n 个整数，每个数一行，对应 n 个询问。
样例
输入数据 1
3
1 10
10 20
5 9
输出数据 1
2
11
0#include<bits/stdc++.h>
using namespace std;
long long a,b,sz[1000001],n,t,s;
int main(){for(int i=1;i<=1000001;i++)//赋值{t=i;while(t!=0){if(t%10==1)s++;t=t/10;}sz[i]=sz[i-1]+s;s=0;}scanf("%lld",&n);for(int i=1;i<=n;i++){scanf("%lld" "%lld",&a,&b);//计算if(a>b) swap(a,b);printf("%lld\n",sz[b]-sz[a-1]);}return 0;
}预告
【类型商店】字符字符串
