1316. 数列操作B
★★ 输入文件：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 ",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; }
2.线段树打标记！
#include<cstdio> #include<string> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=100005; #define ll long long int a[maxn]; int n,m; struct SegmentTree{ int l,r; long long dat; int lazy_tag; }t[maxn<<2]; void Pushdown(int p,int l,int r,int mid){ t[p*2].dat+=t[p].lazy_tag*(mid-l+1); t[p*2+1].dat+=t[p].lazy_tag*(r-mid); t[p*2].lazy_tag+=t[p].lazy_tag; t[p*2+1].lazy_tag+=t[p].lazy_tag; t[p].lazy_tag=0; } void build(int p,int l,int r){ t[p].l=l;t[p].r=r; if(l==r){ t[p].dat=a[l]; return; } int mid=(l+r)>>1; build(p*2,l,mid); build(p*2+1,mid+1,r); t[p].dat=t[p*2].dat+t[p*2+1].dat; } ll Get(int p,int l,int r,int pos){ if(l==r) return t[p].dat; int mid=(l+r)>>1; Pushdown(p,l,r,mid); if(pos<=mid) return Get(p*2,l,mid,pos); else return Get(p*2+1,mid+1,r,pos); } void Add(int p,int l,int r,int s,int tt,ll x){ if(s>r||tt<l) return; if(s<=l&&r<=tt){ t[p].dat+=x*(r-l+1); t[p].lazy_tag+=x; return; } int mid=(l+r)>>1; Pushdown(p,l,r,mid); Add(p*2,l,mid,s,tt,x);Add(p*2+1,mid+1,r,s,tt,x); t[p].dat=t[p*2].dat+t[p*2+1].dat; } 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 ",Get(1,1,n,x)+a[x]); } else{ int s,t,d;scanf("%d%d%d",&s,&t,&d); Add(1,1,n,s,t,d); } } return 0; }