# 树状数组 区间更新（利用了伪线段树） + poj3468题解

xiaoxiao2021-02-28  16

A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072K Total Submissions: 123915 Accepted: 38431 Case Time Limit: 2000MS Description You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval. Input The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000. The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000. Each of the next Q lines represents an operation. "C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000. "Q a b" means querying the sum of Aa, Aa+1, ... , Ab. Output You need to answer all Q commands in order. One answer in a line. Sample Input 10 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4 Sample Output 4 55 9 15 Hint The sums may exceed the range of 32-bit integers. Source POJ Monthly--2007.11.25, Yang Yi //区间更新 #include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstring> using namespace std; const int N=5e5+10; long long sum[N];//前缀和树状数组 long long a[N]; long long n,m; long long ddd[N];//加数树状数组 long long lowbit(long long t) { return t&(-1*t); } void update(long long x,long long v, long long t[]) { //给x的起始位置加v 并更新k数组 for(int i=x; i<=n; i+=lowbit(i)) { t[i]+=v; } } long long getsum(long long x, long long t[]) { //求k数组第i个前缀和 long long ans=0; for(int i=x; i>0; i-=lowbit(i)) ans+=t[i]; return ans; } void refresh_range(long long i,long long j, long long aa) { //给区间i~j中的所有元素加aa，更新对应的前缀和树状数组和加数树状数组 update(i,-(i-1)*aa,sum); update(i,aa,ddd); update(j+1,j*aa,sum); update(j+1,-1*aa,ddd); } long long range_sum(long long i,long long j) { //求i~j的区间和 long long ans=0; ans+=getsum(j,sum)+getsum(j,ddd)*j; ans-=getsum(i-1,sum)+getsum(i-1,ddd)*(i-1); return ans; } int main() { ios::sync_with_stdio(false); while(cin>>n>>m&&n) { for(int i=1; i<=n; i++) { cin>>a[i]; refresh_range(i,i,a[i]); } char s; for(int i=1;i<=m;i++) { cin>>s; if(s=='C') { long long x,y,z; cin>>x>>y>>z; if(x>y) swap(x,y); refresh_range(x,y,z); } else if(s=='Q') { long long x,y; cin>>x>>y; if(x>y) swap(x,y); cout<<range_sum(x,y)<<endl; } } } return 0; }

lazy_tag[i] += a ; //给 x >= i 的所有节点加数均加 a

lazy_tag[j+1] -= a ; // 给 x >j 的所有节点均减 a ，消除 i 位置处理的影响