「数据结构」线段树

线段树($Segment\ Tree$)是一种基于分治思想的__二叉树__形数据结构，可以用于__区间__上的数据维护，它可以维护以下值

• $maxn\ minn$，区间上最大最小值
• $sum$，区间和
• $lmax$，每段上最大前缀和
• $rmax$，每段上最大后缀和
• $……$

和以下操作

• $Add\ x\ y\ k$，把区间$[x,y]$内元素值全加$k$
• $Query\ x\ y$，查询区间$[x,y]$内的某个值

由于线段树会维护一种数据，其他也很好写，所以本篇以__区间和__为例

区间和

在每次$Add$操作中，如果将相关区间的值全部更新，则会把时间复杂度提高到$O(n)$

所以我们可以采取一种__延迟标记__($lazy-tag$)的技巧，如果被标记，则说明本区间内的值被整体加上某个值了

详细方法见代码：

struct SegmentTree {
    struct SegmentTreeNode { //树上的节点
        int l, r;                   //节点表示区间的左右端点
        long long sum, add;         //区间和和add的延迟标记
        #define l(x) tree[x].l      //方便访问
        #define r(x) tree[x].r
        #define sum(x) tree[x].sum
        #define add(x) tree[x].add
    } tree[maxn << 2];
    int a[maxn], n, m;
    void build(int p, int l, int r) { //建树
        l(p) = l, r(p) = r;           //设置左右端点
        if (l == r) { sum(p) = a[l]; return; } //到达叶子节点
        int mid = (l + r) >> 1;
        build(p * 2, l, mid);         //递归构建左右树
        build(p * 2 + 1, mid + 1, r);
        sum(p) = sum(p * 2) + sum(p * 2 + 1); //更新数据，可改为需要维护的多个值的维护方法
    }
    void pushdown(int p) { //下传延迟标记
        if (add(p)) { //如果有标记
            sum(p * 2) += add(p) * (r(p * 2) - l(p * 2) + 1); //sum传至左儿子
            sum(p * 2 + 1) += add(p) * (r(p * 2 + 1) - l(p * 2 + 1) + 1); //右儿子
            add(p * 2) += add(p);      //延迟标记传至左儿子
            add(p * 2 + 1) += add(p);  //右儿子
            add(p) = 0; //本节点延迟标记清零
        }
    }
    void update(int p, int l, int r, int d) { //更新区间内值
        if (l <= l(p) && r >= r(p)) { //完全覆盖
            sum(p) += (long long)d * (r(p) - l(p) + 1); //更新节点信息
            add(p) += d; //打上延迟标记
            return;
        }
        pushdown(p); //下传标记
        int mid = (l(p) + r(p)) >> 1;
        if (l <= mid) update(p * 2, l, r, d);      //递归更新左右
        if (r >  mid) update(p * 2 + 1, l, r, d);
        sum(p) = sum(p * 2) + sum(p * 2 + 1);      //维护数据
    }
    long long query(int p, int l, int r) { //查询操作
        if (l <= l(p) && r >= r(p)) return sum(p); //完全覆盖
        pushdown(p); //下传标记
        int mid = (l(p) + r(p)) >> 1;
        long long ans = 0;
        if (l <= mid) ans += query(p * 2, l, r);     //加上左右部分值
        if (r >  mid) ans += query(p * 2 + 1, l, r);
        return ans;
    }
    #undef add   //防止后续使用add等出现错误
    #undef sum
    #undef l
    #undef r
};

为了使代码简洁，还可以宏定义一些名称

#define lt p<<1     //左孩子
#define rt p<<1|1   //右孩子
#define lson lt,l,mid    //左子树
#define rson rt,mid+1,r  //右子树

$Luogu$模板题目

Luogu P3372 线段树1 (区间增加，区间查询和)

Luogu P3373 线段树2 (区间增加，区间乘数，区间查询和)

$SPOJ$的$GSS$系列

1. SP1043 GSS1 - Can you answer these queries I
2. SP1557 GSS2 - Can you answer these queries II
3. SP1716 GSS3 - Can you answer these queries III
4. SP2713 GSS4 - Can you answer these queries IV
5. SP2916 GSS5 - Can you answer these queries V
6. SP4487 GSS6 - Can you answer these queries VI
7. SP6779 GSS7 - Can you answer these queries VII