区间和线段树封装模板

区间和线段树封装模板，开箱即用
注意：线段树大小最多支持\(2^{30}-1\)个数

声明方法：

• SegSumTree<typename>st，typename为线段树存储的类型（建议只填写整数类型），建立一颗空线段树，后续必须先用rebuild或resize初始化
• SegSumTree<typename>st(n) 建立一颗定义了长度的空线段树，n为线段树维护的数组长度
• SegSumTree<typename>st(n,arr[]) 建立一颗给定了长度和所维护数组的线段树，n为线段树维护的数组长度，arr为线段树维护的数组

功能：

• update_seg(l,r,v) l到r区间增加v
• update_poi(k,v) 第k个数单点增加v
• query_seg(l,r) 返回l到r区间和
• query_poi(k) 返回第k个数的值
• empty() 返回一个布尔值，1为非空，0为空
• size() 返回线段树维护的数组长度，并非线段树数组自身大小
• clear() 清空线段树，该函数并非只使线段树维护的数清零，而是完全初始化
• build(n,arr[]) 建立线段树，n为维护的数组长度，arr为数组，使用该函数需保证线段树为空
• resize(n) 定义线段树大小，n为维护的数组长度，使用该函数需保证线段树为空

template<class T>
class SegSumTree{
    private:
        int n;
        vector<T>sum,add;
        inline void pri_pushup(int pos){
            sum[pos]=sum[pos<<1]+sum[pos<<1|1];
        }
        inline void pri_pushdown(int pos,int l,int r){
            if(add[pos]){
                T len=r-l+1;
                add[pos<<1]+=add[pos];
                sum[pos<<1]+=add[pos]*(len-len/2);
                add[pos<<1|1]+=add[pos];
                sum[pos<<1|1]+=add[pos]*(len/2);
                add[pos]=0;
            }
        }
        void pri_build(int pos,int l,int r,T arr[]){
            if(l==r){
                add[pos]=0;
                sum[pos]=arr[l];
                return;
            }
            int mid=(l+r)/2;
            pri_build(pos<<1,l,mid,arr);
            pri_build(pos<<1|1,mid+1,r,arr);
            pri_pushup(pos);
        }
        void pri_update_seg(int pos,int l,int r,int ll,int rr,T val){
            if(l>rr || r<ll) return;
            if(ll<=l && r<=rr){
                add[pos]+=val;
                sum[pos]+=val*(r-l+1);
                return;
            }
            pri_pushdown(pos,l,r);
            int mid=(l+r)/2;
            if(l<=mid) pri_update_seg(pos<<1,l,mid,ll,rr,val);
            if(mid<r) pri_update_seg(pos<<1|1,mid+1,r,ll,rr,val);
            pri_pushup(pos);
        }
        void pri_update_poi(int pos,int l,int r,int k,T val){
            if(!(l<=k && k<=r)) return;
            if(l==r && l==k){
                sum[pos]+=val;
                return;
            }
            int mid=(l+r)/2;
            if(k<=mid) pri_update_poi(pos<<1,l,mid,k,val);
            else pri_update_poi(pos<<1|1,mid+1,r,k,val);
            pri_pushup(pos);
        }
        T pri_query_seg(int pos,int l,int r,int ll,int rr){
            if(l>rr || r<ll) return 0;
            if(ll<=l && r<=rr){
                return sum[pos];
            }
            pri_pushdown(pos,l,r);
            T res=0;
            int mid=(l+r)/2;
            if(l<=mid) res+=pri_query_seg(pos<<1,l,mid,ll,rr);
            if(mid<r) res+=pri_query_seg(pos<<1|1,mid+1,r,ll,rr);
            return res;
        }
        T pri_query_poi(int pos,int l,int r,int k){
            if(!(l<=k && k<=r)) return 0;
            if(l==r && l==k){
                return sum[pos];
            }
            pri_pushdown(pos,l,r);
            int mid=(l+r)/2;
            if(k<=mid) return pri_query_poi(pos<<1,l,mid,k);
            else return pri_query_poi(pos<<1|1,mid+1,r,k);
        }
    public:
        SegSumTree(){
            n=0;
        }
        SegSumTree(int maxn){
            n=maxn;
            sum.resize(n<<2);
            add.resize(n<<2);
        }
        SegSumTree(int maxn,T arr[]){
            n=maxn;
            sum.resize(n<<2);
            add.resize(n<<2);
            pri_build(1,1,n,arr);
        }
        inline void clear(){
            n=0;
            sum.clear();
            add.clear();
        }
        inline bool empty(){
            return (n==0);
        }
        inline int size(){
            return n;
        }
        inline void resize(int maxn){
            n=maxn;
            sum.resize(n<<2);
            add.resize(n<<2);
        }
        inline void build(int maxn,T arr[]){
            n=maxn;
            sum.resize(n<<2);
            add.resize(n<<2);
            pri_build(1,1,n,arr);
        }
        inline void update_seg(int l,int r,T val){
            pri_update_seg(1,1,n,l,r,val);
        }
        inline void update_poi(int k,T val){
            pri_update_poi(1,1,n,k,val);
        }
        inline T query_seg(int l,int r){
            return pri_query_seg(1,1,n,l,r);
        }
        inline T query_poi(int k){
            return pri_query_poi(1,1,n,k);
        }
};