★★ 输入文件：shulieb.in 输出文件：shulieb.out 简单对比
时间限制：1 s 内存限制：128 MB
假设有一个大小为 n(n≤100000) 整数数列 A，支持如下两种操作：
1. 将 Ai,Ai+1,…,Aj 的值均增加 d
2. 查询 Ai 的值
根据操作要求进行正确操作并输出结果。
输入文件第一行一个整数 n，
第二行为 n 个整数，表示数列 A 中各项的初始值。
第三行为一个整数 m ，表示操作数。下接 m 行，每行描述一个操作，有如下两种情况：
ADD i j d（将 Ai,Ai+1,…,Aj(1≤i,j≤n) 的值均增加一个整数 d）
QUERY s（表示查询 As 的值）
对于每一个询问，输出查询到的结果。
4 1 4 2 3 3 QUERY 1 ADD 2 2 50 QUERY 2
1 54
做法一：用树状数组存储差分数组
代码如下
#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #define maxn 100005 using namespace std; int n,m; int a[maxn],sum[maxn]; int lowbit(int x){ return x&(-x); } #define ll long long void Add(int x,int d){//存的是差分数组 while(x<=n){sum[x]+=d;x+=lowbit(x); } } long long Sum(int x){ long long ret=0; while(x>0){ ret+=sum[x];x-=lowbit(x);} return ret; } int main() { freopen("shulieb.in","r",stdin);freopen("shulieb.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&m); for(int i=1;i<=m;i++){ string s;cin>>s; if(s[0]==‘Q‘){ int x;scanf("%d",&x); printf("%lld\n",Sum(x)+a[x]); } else{ int l,r,x;scanf("%d%d%d",&l,&r,&x); Add(l,x);Add(r+1,-x); } } return 0; }
原文：https://www.cnblogs.com/Tidoblogs/p/11306966.html