但是板子2卡
@[tigatm](/space/show?uid=120594)
by Jelly_Goat @ 2019-02-17 16:59:03
@[Jelly_Goat](/space/show?uid=122927) 事实上板子2也不卡（
by Juan_feng @ 2019-02-17 17:03:50
拿模板st表和模板树状数组练线段树....
by 龙·海流 @ 2019-02-17 17:24:04
为什么我线段树超时了QAQ
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string.h>
#define ll long long
using namespace std;
ll Left(ll a){return a*2;}
ll Right(ll a){return a*2+1;}
ll i,j,k,m,n,a[1000001],ans[1000001],Lazy[1000001];
void PushUp(ll now)
{
ans[now]=ans[Left(now)]+ans[Right(now)];
}
void Build(ll now,ll l,ll r)
{
if(l==r){ans[now]=a[l];return;}
ll mid=(l+r)/2;
Build(Left(now),l,mid);
Build(Right(now),mid+1,r);
PushUp(now);
}
void Function(ll now,ll l,ll r,ll Add)
{
Lazy[now]+=Add;
ans[now]+=Add*(r-l+1);
}
void PushDown(ll now,ll l,ll r)
{
ll mid=(l+r)/2;
Function(Left(now),l,mid,Lazy[now]);
Function(Right(now),mid+1,r,Lazy[now]);
Lazy[now]=0;
}
void Data(ll NowL,ll NowR,ll l,ll r,ll now,ll Add)
{
if(NowL<=l&&NowR>=r)
{
ans[now]+=Add*(r-l+1);
Lazy[now]+=Add;
return;
}
PushDown(now,l,r);
ll mid=(l+r)/2;
if(NowL<=mid)Data(NowL,NowR,l,mid,Left(now),Add);
if(NowR>mid)Data(NowL,NowR,mid+1,r,Right(now),Add);
PushUp(now);
}
ll Query(ll NowL,ll NowR,ll l,ll r,ll now)
{
ll Return=0;
if(NowL<=l&&NowR>=r)return ans[now];
ll mid=(l+r)/2;
PushDown(now,l,r);
if(NowL<=mid)Return+=Query(NowL,NowR,l,mid,Left(now));
if(NowR>mid)Return+=Query(NowL,NowR,mid+1,r,Right(now));
return Return;
}
int main()
{
cin>>n>>m;
for(i=1;i<=n;i++)cin>>a[i];
Build(1,1,n);
for(i=1;i<=m;i++)
{
int Read;
cin>>Read;
if(Read==1)
{
int f,l,Add;
cin>>f>>Add;
l=f;
Data(f,l,1,n,1,Add);
}
if(Read==2)
{
int f,l;
cin>>f>>l;
cout<<Query(f,l,1,n,1)<<endl;
}
}
return 0;
}
```
by Limit @ 2019-03-04 17:54:28
然而平衡树也能跑得飞快（
by 小菜鸟 @ 2019-06-19 09:29:00