2018-team4-modules-普通线段树

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
struct segTree{
        int sum[maxn<<2],tag[maxn<<2],mx[maxn<<2];
        inline void pushdown(int rt,int l,int r){
            if(rt == 0 || tag[rt] == 0) return ;
            int mid = l+r >> 1;
            sum[rt<<1] += tag[rt]*(mid - l + 1);
            sum[rt<<1|1] += tag[rt]*(r - mid);
            mx[rt<<1] += tag[rt];
            mx[rt<<1|1] += tag[rt];
            tag[rt<<1] += tag[rt];
            tag[rt<<1|1] += tag[rt];
            tag[rt] = 0;
        }
        void modify(int rt,int l,int r,int L,int R,int d){
            if(L <= l && r <= R){
                tag[rt] += d;
                sum[rt] += d*(r - l + 1);
                mx[rt] += d;
                return ;
            }
            int mid = l+r >> 1;pushdown(rt,l,r);
            if(L <= mid) modify(rt<<1,l,mid,L,R,d);
            if(R >  mid) modify(rt<<1|1,mid+1,r,L,R,d);
            sum[rt] = sum[rt<<1] + sum[rt<<1|1];
            mx[rt] = max(mx[rt<<1],mx[rt<<1|1]);
        }
        int query_max(int rt,int l,int r,int L,int R){
            if(L <= l && r <= R) return mx[rt];
            int mid = l+r >> 1;pushdown(rt,l,r);
            if(R <= mid) return query_max(rt<<1,l,mid,L,R);
            if(L >  mid) return query_max(rt<<1|1,mid+1,r,L,R);
            return max(query_max(rt<<1,l,mid,L,R),query_max(rt<<1|1,mid+1,r,L,R));
        }
        int query_sum(int rt,int l,int r,int L,int R){
            if(L <= l && r <= R) return sum[rt];
            int mid = l+r >> 1;pushdown(rt,l,r);
            if(R <= mid) return query_sum(rt<<1,l,mid,L,R);
            if(L >  mid) return query_sum(rt<<1|1,mid+1,r,L,R);
            return query_sum(rt<<1,l,mid,L,R) + query_sum(rt<<1|1,mid+1,r,L,R);
        }
    };
}
}}}

struct segTree{
        int sum[maxn<<2],tag[maxn<<2],mx[maxn<<2];
        inline void pushdown(int rt,int l,int r){
            if(rt == 0 || tag[rt] == 0) return ;
            int mid = l+r >> 1;
            sum[rt<<1] += tag[rt]*(mid - l + 1);
            sum[rt<<1|1] += tag[rt]*(r - mid);
            mx[rt<<1] += tag[rt];
            mx[rt<<1|1] += tag[rt];
            tag[rt<<1] += tag[rt];
            tag[rt<<1|1] += tag[rt];
            tag[rt] = 0;
        }
        void modify(int rt,int l,int r,int L,int R,int d){
            if(L <= l && r <= R){
                tag[rt] += d;
                sum[rt] += d*(r - l + 1);
                mx[rt] += d;
                return ;
            }
            int mid = l+r >> 1;pushdown(rt,l,r);
            if(L <= mid) modify(rt<<1,l,mid,L,R,d);
            if(R >  mid) modify(rt<<1|1,mid+1,r,L,R,d);
            sum[rt] = sum[rt<<1] + sum[rt<<1|1];
            mx[rt] = max(mx[rt<<1],mx[rt<<1|1]);
        }
        int query_max(int rt,int l,int r,int L,int R){
            if(L <= l && r <= R) return mx[rt];
            int mid = l+r >> 1;pushdown(rt,l,r);
            if(R <= mid) return query_max(rt<<1,l,mid,L,R);
            if(L >  mid) return query_max(rt<<1|1,mid+1,r,L,R);
            return max(query_max(rt<<1,l,mid,L,R),query_max(rt<<1|1,mid+1,r,L,R));
        }
        int query_sum(int rt,int l,int r,int L,int R){
            if(L <= l && r <= R) return sum[rt];
            int mid = l+r >> 1;pushdown(rt,l,r);
            if(R <= mid) return query_sum(rt<<1,l,mid,L,R);
            if(L >  mid) return query_sum(rt<<1|1,mid+1,r,L,R);
            return query_sum(rt<<1,l,mid,L,R) + query_sum(rt<<1|1,mid+1,r,L,R);
        }
    };
}