★★★ 输入文件：shuliec.in 输出文件：shuliec.out 简单对比
时间限制：1 s 内存限制：128 MB
假设有一个长度为 n(n≤100000) 的数列 A，支持如下两种操作：
1. 将 Ai,Ai+1,…,Aj 的值均增加 d
2. 查询 As+As+1+?+At(s≤t) 的值。
根据操作要求进行正确操作并输出结果。
第一行为一个正整数 n，表示数列的大小。
第二行有 n 个整数，表示数列 A 各项的初始值。
第三行为一个整数 m ，表示操作的个数。
下面是 m 行，每行描述一个操作：
ADD i j d（将 Ai,Ai+1,…,Aj(1≤i,j≤n) 的值均增加一个整数 d）
SUM s t（表示查询 As+?+At 的值）
对于每一次询问，输出查询到的结果。
4 1 4 2 3 3 SUM 1 3 ADD 2 2 50 SUM 2 3
7 56
所有答案小于 4611686018427387904
加强 10 组极限数据，未全部重测 by rvalue 2018.2.26
还是线段树而已
#include<cstdio> #include<string> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=100005; #define ll long long ll a[maxn]; int n,m; struct SegmentTree{ int l,r; long long dat; long long 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 s,int tt){ if(s>r||tt<l) return 0; if(s<=l&&r<=tt) return t[p].dat; int mid=(l+r)>>1; Pushdown(p,l,r,mid); return Get(p*2,l,mid,s,tt)+ Get(p*2+1,mid+1,r,s,tt); } 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("shuliec.in","r",stdin);freopen("shuliec.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); scanf("%d",&m); build(1,1,n); for(int i=1;i<=m;i++){ string s;cin>>s; if(s[0]==‘S‘){ int l,r;scanf("%d%d",&l,&r); printf("%lld\n",Get(1,1,n,l,r)); } else{ int s,t; ll d; scanf("%d%d%lld",&s,&t,&d); Add(1,1,n,s,t,d); } } return 0; }
还有一个
标记永久化线段树
原文：https://www.cnblogs.com/Tidoblogs/p/11307395.html