应该是做的最认真的模板了。。。
namespace xds{
template<class T,const int MYMAXSIZE,T (*fun)(T a,T b)>
class STree{
private:
T t[MYMAXSIZE<<2],tag[MYMAXSIZE<<2],a[MYMAXSIZE];
int num;
inline const int ls(const int x){return x<<1;}
inline const int rs(const int x){return x<<1|1;}
void push_up(const int x){t[x]=fun(t[ls(x)],t[rs(x)]);}
inline void f(const T&x,const int&l,const int&r,const T&k){
tag[x]=fun(tag[x],k);
t[x]=fun(t[x],k*(r-l+1));
}
inline void push_down(const T&x,const int&l,const int&r){
const T mid=(l+r)>>1;
f(ls(x),l,mid,tag[x]);
f(rs(x),mid+1,r,tag[x]);
tag[x]=0;
}
inline void update(const int&l,const int&r,const T&k,const int&ql,const int&qr,const int&x){
if(l<=ql&&r>=qr){//完全覆盖
t[x]=fun(t[x],k*(qr-ql+1));
tag[x]=fun(tag[x],k);
return;
}
push_down(x,ql,qr);
const T mid=(ql+qr)>>1;
if(l<=mid)update(l,r,k,ql,mid,ls(x));
if(r>mid)update(l,r,k,mid+1,qr,rs(x));
push_up(x);
}
inline T query(const int l,const int r,const int ql,const int qr,const int x){
T res=0;
int mid=(ql+qr)>>1;
if(l<=ql&&qr<=r)return t[x];
push_down(x,ql,qr);
if(l<=mid)res+=query(l,r,ql,mid,ls(x));
if(r>mid)res+=query(l,r,mid+1,qr,rs(x));
return res;
}
public:
STree():num(MYMAXSIZE-1){}
STree(const int n):num(n){}
inline T &operator[](const int i){return a[i];}
void build(const int x=1,const int l=1,int r=-1){
if(r<0)r=num;
tag[x]=0;
if(l==r){t[x]=a[l];return;}
const int mid=(l+r)>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
push_up(x);
}
inline void update(const int&l,const int&r,const T&k){
push_down(1,1,num);
const T mid=(1+num)>>1;
if(l<=mid)update(l,r,k,1,mid,ls(1));
if(r>mid)update(l,r,k,mid+1,num,rs(1));
push_up(1);
}
inline T query(const int l,const int r){
T res=0;
int mid=(1+num)>>1;
if(l<=1&&num<=r)return t[1];
push_down(1,1,num);
if(l<=mid)res+=query(l,r,1,mid,ls(1));
if(r>mid)res+=query(l,r,mid+1,num,rs(1));
return res;
}
inline int&getnum(){return num;}
inline T&scan(int x){return a[x];}
};
}
- 用法：
xds::STree<线段树所存储的数据类型,数据范围（线段树最大存储的数据数量）,操作方法（函数）> - 注意：
- 创建线段树时能且只能使用以下两种方法 （如果发现更多使用方法或修改方法求评论或私信，不胜感激） ：
xds::STree<int,100009,add> *tree=new xds::STree<线段树所存储的数据类型,数据范围（线段树最大存储的数据数量）,操作方法（函数）>(输入的数据个数，即数列数字的个数); xds::STree<线段树所存储的数据类型,数据范围（线段树最大存储的数据数量）,操作方法（函数）> tree();
- 例子：P3372 【模板】线段树 1：
#include<bits/stdc++.h>
using namespace std;
//【此处补充上述模板，由于代码过长，此处省略】
long long add(long long a,long long b){
return a+b;
}
inline long long read(){
register long long x = 0, t = 1;
register char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*t;
}
int main(){
long long n=read(),m=read(),op,x,y,k;
xds::STree<long long,100009,add> *tree=new xds::STree<long long,100009,add>(n);
// xds::STree<int,100009,add> tree();tree.num=n;
for(int i=1;i<=n;i++)tree->scan(i)=read();
// for(int i=1;i<=n;i++)tree[i]=read();
tree->build();
while(m--){
op=read();
switch(op){
case 1:
x=read(),y=read(),k=read();
tree->update(x,y,k);
break;
case 2:
x=read(),y=read();
printf("%lld\n",tree->query(x,y));
}
}
}
注释处暂时由bug，抽空整。
鸣谢：