线段树是一种基于分治思想的二叉树结构，用于在区间上进行信息统计。与按照二进制位进行区间划分的树状数组相比，线段树是一种更加通用的结构。

这时候有的同学就要问了：ε=(´ο｀*)))唉，伍衍伍衍，那么我们为什么还要学树状数组呢？

你说呢 原因是：由于其代码复杂度远远超过树状数组，所以能用树状数组写的就不要用线段树写（关键原因写完调一整天直接红温了）：

1.线段树的每个节点都代表一个区间。

2.线段树具有唯一的根节点，代表的区间是整个统计范围，如 [1,n] 。

3.线段树的每个叶节点都代表一个长度为1的元区间 [x,x]。

4.对于每个内部节点 [l,r]，它的左子节点是 [l,mid]，右子节点是 [mid+1,r]，其中 mid=(l+r)/2（向下取整）。

线段树示意图：

由于是二叉树，所以我们可以直接使用"父子两倍"命名法。

（即父节点 $u$ 的两个子节点分别为 $u\times 2$ 和 $u\times 2+1$）

但是由于线段树的复杂度通常过高，所以我们用位运算（u<<1 和 u<<|1）来替代原本的 $u\times 2$ 和 $u\times 2+1$。

这时候有的同学就又要问了：ε=(´ο｀*)))唉，伍衍伍衍，这里为什么要用 |1 而不用 +1 呢？

因为，一个数 $\times 2$ 后一定是一个偶数，即二进制下的最后一位是 $0$，而 |1 就相当于 +1。

线段树的建树

线段树的建树线段树的基本用途是对序列进行维护，支持查询与修改指令。给定一个长度为 n 的序列 a，我们可以在区间[1,n]上建立一棵线段树，每个叶节点 [i,i] 保存 a[i]的值。线段树的二叉树结构可以很方便地从下往上传递信息。以区间最大值问题为例，记 mx(l,r) 等于$max_{l≤i≤r}\{A[i]\}$，显然dat(l,r)=max(mx(l,mid),mx(mid+1,r))。

基础建树模版：

struct P{
    long long l,r,v;
};
P tree[N*4];
void build(long long u,long long l,long long r){
    if(l==r) tree[u]={l,r,0};
    else{
        tree[u]={l,r,0};
        long long mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
    }
}

这时候有细心的同学就又双要问了：ε=(´ο｀*))) 唉伍衍伍衍，这里的数组为什么要开四倍呢？

请看VCR 解析如下：

所以我们要开四倍的数组（看不懂就背下来开 $4$ 倍数组）。

动态开点可以只开两倍的数组，这远远超出了我们的讨论范畴（有动态开点的话，难度【提高+/省选-】起步，一般为【省选/NOI-】）（反正现在也用不到）

线段树的单点修改

单点修改是一条形如 "C x v" 的指令，表示把 a[x] 的值修改为 v 。在线段树中，根节点（编号为 1 的节点）是执行各种指令的入口。我们需要从根节点出发，递归找到代表区间 [x,x] 的叶节点，然后从下往上更新 [x,x] 以及它的所有祖先节点上保存的信息，如下图所示。时间复杂度为 $O(logN)$。

单点修改模版：

void pushup(long long u){
    tree[u].v=max(tree[u<<1].v,tree[u<<1|1].v);
}
void modify(long long u,long long x,long long c){
    if(tree[u].l==x&&tree[u].r==x) tree[u]={x,x,c};
    else{
        long long mid=tree[u].l+tree[u].r>>1;
        if(x<=mid) modify(u<<1,x,c);
        else modify(u<<1|1,x,c);
        pushup(u);
    }
}

线段树的区间查询

区间查询是一条形如"Q l r"的指令，例如查询序列A在区间 [l,r] 上的最大值，即 $max_{l≤i≤r}\{A[i]\}$。我们只需要从根节点开始，递归执行以下过程：

1.若[r]完全覆盖了当前节点代表的区间，则立即回溯，并且该节点的 mx 值为候选答案。

2.若左子节点与 [l,r] 有重叠部分，则递归访问左子节点。

3.若右子节点与 [l,r] 有重叠部分，则递归访问右子节点。

$2$ 与 $3$ 可以同时满足。

区间查询代码：

long long query(long long u,long long l,long long r){
    if(l<=tree[u].l&&r>=tree[u].r) return tree[u].v;
    else{
        long long mid=tree[u].l+tree[u].r>>1;
        if(r<=mid) return query(u<<1,l,r);
        else if(l>mid) return query(u<<1|1,l,r);
        else{ // 2 和 3
            return max(query(u<<1,l,r),query(u<<1|1,l,r));
        }
    }
}

其时间复杂度分析如下：

所以，其也能在 $O(logN)$ 的时间复杂度之内完成查询。

最后，我们终于写完了基础的 难得要命的 线段树。

至此，线段树已经能够 $ST$ 表算法一样处理区间最值问题，并且还支持动态修改某个数的值。同时，线段树也已经能支持上一节中树状数组的单点增加与查询前缀和指令。在讨论区间修改之前，我们先来通过几道例题加深对线段树的印象。

$T1$

题面：

略（自己看）

思路及代码：

线段树见上面模版，主函数调用方式如下

long long last=0;
long long m,p,n=0;
cin >> m >> p;
build(1,1,m);
while(m--){
    string s;
    long long t;
    cin >> s >> t;
    if(s=="A"){
        modify(1,++n,(t+last)%p); // (t+last)%p 传参为题目要求，主要题面中没有给出
    }else{
        last=query(1,n-t+1,n);
        cout << last << endl;
    }
}

$T2$

题面：

思路：在线段树内，我们维护区间左端点 $l$，区间右端点 $r$，区间和 $sum$，区间最大前缀 $lmax$，区间最大后缀 $rmax$，区间最大子序和 $v$。经过分析可得：

void pushup(P &u,P &l,P &r){
    u.sum=l.sum+r.sum;
    u.lsum=max(l.lsum,l.sum+r.lsum);
    u.rsum=max(r.rsum,r.sum+l.rsum);
    u.tsum=max(l.tsum,max(r.tsum,l.rsum+r.lsum));
}
void pushup(long long u){
    pushup(tree[u],tree[u<<1],tree[u<<1|1]);
}

在其它函数中按此式修改即可。