线段树

介绍

线段树是基于分治思想的二叉树，用来维护区间信息（和，最值，gcd等）可以在logn的时间内执行区间修改和查询
线段树中的每个叶子节点存储元素本身，非叶子节点存储区间内元素统计值。

节点数组 tr[]

结构体包含三个变量 l,r,sum
lr为区间左右端点，sum为区间和

树的建立

父亲节点的编号为p，左孩子节点为2p，右孩子节点为2p+1

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

递归的方式建树

void build(int p,int l,int r){
    tr[p] = {l,r,w[l]}//w[]数组存储元素原来的值
    if(l == r ) return;//叶子节点返回
    int mid = i+r>>1;//不是叶子节点分裂
    build(lc,l,mid);
    build(rc,mid+1,r);
    tr[p].sum = tr[lc].sum + tr[rc].sum;
}

点修改

从根节点进入，递归找到叶子节点[x,x] 把该节点的值修改，从下往上更新祖先节点的统计值

void update(int p,int x,int k){
    if(tr[p].l == x && tr[p].r == x){
        tr[p].sum +=k;
        return ;
    }
    int mid = tr[p].l+tr[p].r >>1;//向下分裂查找
    if(x<=mid) update(lc,x,k);
    else  update(rc,x,k);
    tr[p].sum = tr[lc].sum + tr[rc].sum;//更新父节点
}

区间查询

从根节点进入，递归以下过程

1查询区间[x,y]是否完全覆盖当前节点，覆盖则立即回溯并返回节点值

2若左子节点有重叠递归访问左子树

3若右子节点有重叠递归访问右子树

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