线段树（懒惰标记）

可以用用来维护区间信息（区间和，区间最值，区间GCD等），可以在$loogn$的时间内执行区间查询和区间查询。

线段树中每个叶子节点存储元素本身，非叶子节点存储区间内的元素的统计值。

1. 节点数组$tr[]$

结构体包含三个变量：$l$,$r$,$sum$。，分别是区间的左右端点区间和。

2. 递归建树

父亲节点的编号是p，左孩的编号是2*p，右孩是2*p+1。

#defind lc p << 1
#defind rc p << 1 | 1
struct node{
    int l, r, sum ;
}tr[N*4] ;

void build(int p, int l, int r){
    tr[p] = {l,r,w[l]} ;//如果不是叶子节点那么在之后的计算会覆盖
    if(l == r) return ;
    int m = l + r >> 1 ;
    build(lc,l,m);
    build(rc,m+1,r);
    tr[p].sum = tr[lc].sum + tr[rc].sum ;
}

---

线段树为什么空间大小开 $4*n$

如果叶子节点的数量恰好是2的幂（$2^m$），那么空间开$2*m-1$即可。

但如果不是2的幂，是$2^m + k$，那么节点的最大编号就是

---

点修改

从根节点进入，递归找到叶子节点[x,x]，把该节点的值增加$k$。然后从下往上更新祖先节点上的统计值。

void update(int p, int x, int k){
    if(tr[p].l == x && tr[p].r == x){
        tr[p].sum += k ;
        return ;
    }
    int m = tr[p].l + tr[p].r >> 1 ;
    if(x <= m) update(lc, x, k) ;
    if(x > m) update(rc, x, k) ;
    tr[p].sum = tr[lc].sum + tr[rc].sum ;
}

---

区间查询

拆分与拼凑的思想。例如，查询区间[4,9]可以拆分成[4,5]，[6,8]，[9,9]，

从根节节点进入，递归执行：

1. 如果查询区间[x,y]完全覆盖当前节点区间，则，立即回溯，并返回该节点的sum值。
2. 若左子节点与[x,y]有重叠，则递归访问左子树。
3. 若右子节点与[x,y]有重叠，则递归访问右子树。

int querry(int p, int x, int y){
    if(x <= tr[p].l && y >= tr[p].r){
        return tr[p].sum ;
    }
    int sum = 0 ;
    int m = tr[p].l + tr[p].r >> 1 ;
    if(x <= m) sum += querry(lc, x, m) ;
    if(y > m) sum += querry(rc, m + 1, y) ;
    return sum ;
}

---

区间修改

懒惰修改，当[x,y]完全覆盖节点区间[a,b]时，先修改该区间的$sum$值，再打上一个懒惰标记，然后立即返回。等到下一次需要时，在下传懒惰标记，这样修改和查询都是$logn$。

void pushup(int p){
    tr[p].sum = tr[lc].sum + tr[rc].sum ;
}

void pushdown(int p){
    if(tr[p].add){
        tr[lc].sum += tr[p].add * (tr[lc].r - tr[lc].l + 1) ;
        tr[rc].sum += tr[p].add * (tr[rc].r - tr[rc].l + 1) ;
        tr[lc].add += tr[p].add ;
        tr[rc].add += tr[p].add ;
        tr[p].add = 0 ;
    }
}

void update(int p, int l, int r, int k){
    if(l <= tr[p].l && r >= tr[p].r){
        tr[p].sum += (tr[p].r - tr[p].l + 1) * k ;
        tr[p].add += k ;
        return ;
    }
    int m = (tr[p].l + tr[p].r) >> 1 ;
    pushdown(p) ;
    if(l <= m) update(lc, l, r, k) ;
    if(r > m) update(rc, l, r, k) ;
    pushup(p) ;
}

懒惰标记的查询

int querry(int p, int l, int r){
    if(l <= tr[p].l && r >= tr[p].r){
        return tr[p].sum ;
    }
    int m = (tr[p].l + tr[p].r) >> 1 ;
    pushdown(p) ;
    int sum = 0 ;
    if(l <= m)  sum += querry(lc, l, r) ;
    if(r > m) sum += querry(rc, l, r) ;
    return sum ;
}