这道题可以用珂朵莉树做，但是由于数据比较不随机，而我也没有手写一颗平衡树，所以就被卡掉了，只拿了70分。
珂朵莉树是一种基于平衡树的（伪）高效数据结构。
它的核心操作是推平一段区间。
简而言之，就是把之前的零零碎碎的都干掉，用一个美而饱满的大区间取代。
然后我们更新操作和查询操作就暴力遍历一遍，统计一下和就可以了。
Split操作
inline set<node>::iterator split(int pos){
set<node>::iterator it=s.lower_bound(node(pos));
if(it!=s.end()&&it->l==pos)return it;
--it;
int L=it->l,R=it->r;long long V=it->v;
s.erase(it),s.insert(node(L,pos-,V));
return s.insert(node(pos,R,V)).first;
}split操作就是获得区间的迭代器。
所以我们要先找到pos在哪里（也就是it）。
然后把它拆掉，再合在一起。
在这个过程中我们就可以拿到迭代器。（干什么等会说）
Update操作
inline void update(int l,int r,long long val=){
set<node>::iterator itl=split(l),itr=split(r+);
for(;itl!=itr;++itl)itl->v+=val;
}现在刚才的split就派上用场了。
我们现在相当于是获得了区间的两端（也是区间）。
然后暴力遍历一下，给每个区间都打一个标记。
Query操作
inline long long query(int l,int r){
set<node>::iterator itl=split(l),itr=split(r+);
long long ans=;
for(;itl!=itr;++itl)ans+=(itl->r-itl->l+)*itl->v;
return ans;
}收集一下标记加在一起就可以了，思路和update一样。
70分代码如下：
3741ms 2368kb
#include<bits/stdc++.h>
using namespace std;
namespace StandardIO{
template<typename T>inline void read(T& x){
x=;T f=;char c=getchar();
for(;c<''||c>'';c=getchar())if(c=='-')f=-;
for(;c>=''&&c<='';c=getchar())x=x*+c-'';
x*=f;
}
template<typename T>inline void write(T x){
if(x<)putchar('-'),x*=-;
if(x>=)write(x/);
putchar(x%+'');
}
}
using namespace StandardIO;
namespace ChthollyTree{
struct Tree{
private:
struct node{
int l,r;mutable long long v;
node(int L,int R=-,long long V=):l(L),r(R),v(V){}
bool operator < (const node &o)const{
return l<o.l;
}
};
set<node>s;
inline set<node>::iterator split(int pos){
set<node>::iterator it=s.lower_bound(node(pos));
if(it!=s.end()&&it->l==pos)return it;
--it;
int L=it->l,R=it->r;long long V=it->v;
s.erase(it),s.insert(node(L,pos-,V));
return s.insert(node(pos,R,V)).first;
}
inline void update(int l,int r,long long val=){
set<node>::iterator itl=split(l),itr=split(r+);
for(;itl!=itr;++itl)itl->v+=val;
}
inline long long query(int l,int r){
set<node>::iterator itl=split(l),itr=split(r+);
long long ans=;
for(;itl!=itr;++itl)ans+=(itl->r-itl->l+)*itl->v;
return ans;
}
public:
Tree(){}
~Tree(){}
inline void Init(int n){
s.insert(node(,n));
}
inline void Update(int l,int r,long long val){
update(l,r,val);
}
inline int Query(int l,int r){
return query(l,r);
}
};
}
using namespace ChthollyTree;
namespace Solve{
const int N=;
int n,m;
int sum[N];
Tree ljz;
inline void solve(){
read(n),read(m);
ljz.Init(n);
for(register int i=;i<=n;++i){
int tmp;read(tmp);
sum[i]=sum[i-]+tmp;
}
while(m--){
int op,x,y,z;
read(op),read(x),read(y);
if(op==){
read(z);
ljz.Update(x,y,z);
}else{
write(ljz.Query(x,y)+sum[y]-sum[x-]),putchar('\n');
}
}
}
}
using namespace Solve;
int main(){
solve();
}