线段树模板

应该是做的最认真的模板了。。。

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<线段树所存储的数据类型,数据范围（线段树最大存储的数据数量）,操作方法（函数）>
• 注意：

1. 创建线段树时能且只能使用以下两种方法 （如果发现更多使用方法或修改方法求评论或私信，不胜感激） ：

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，抽空整。

鸣谢：

1. 皎月半洒花管理大大的题解