【C++】线段树

线段树是一种特殊的数据结构，他适用于进行区间RMQ问题。线段树的逻辑结构是一颗二叉树，叶子节点统计的是端点信息，而其余父节点统计的是所有子结点的信息，父结点也就构成了一个个统计区间，这些区间就像是线段，线段树因此得名。

首先，线段树是一颗平衡二叉树，因此搜索效率极高。通常，线段树是一颗普通的平衡二叉树，这种二叉树实现较为复杂，如下图所示：

（图片来自网络，侵删）

zkw大佬在《统计的力量》PPT中介绍了一种更易于实现的线段树，这种线段树一般也被称为zkw线段树。zkw线段树是一颗满二叉树，可以直接线性存储，本文也讲解此类线段树。

zkw线段树是一颗满二叉树，叶子节点也就是端点，如果无法构建满二叉树，则扩充叶子结点至满二叉树。

以存储区间和为例，如下是存储 1 ∼ 6 1sim 6 1∼6且值为 1 , 1 , 2 , 3 , 4 , 2 1,1,2,3,4,2 1,1,2,3,4,2区间和的线段树结构：

如上图所示，直接采用数组存储满二叉树。

int tree[MAXN>>2];//扩充大小到4倍保证够用
int n=0,M=0;//原数组长度和叶子个数

以求和为例，直接往叶子结点输入即可,然后调整非叶结点。

void build(int n){
    for(M=1;M>=1);
    //M是每一层第一个下标，本层有2M-M=M个结点，至少保证有n+2个结点
    for(int i=M+1;i<=M+n;i++) cin>>tree[i];//输入
    //调整
    for(int i=M-1;i;i--) tree[i]=tree[i>>1]+tree[i>>1|1];
}

注意到叶子输入从 M + 1 M+1 M+1开始，这是因为zkw线段树是计算的开区间，左端点 M M M不使用是为开区间计算做准备，其实最右侧的叶结点也是不存在的，所以要存下zkw线段树需要保证最底层有 n + 2 n+2 n+2个结点。

至此，zkw线段树构建完成。

直接自底向上更新。更新叶结点后，逐层往上更新父节点。

void add(int k,int v){
    tree[M+k]+=v;
    for(int i=(M+k)/2;i;i>>=1)//i/=2等于i>>=1
        tree[i]=tree[2*i]+tree[2*i+1];
}

线段树的 [ l , r ] [l,r] [l,r]查询一般写成开区间 ( l − 1 , r + 1 ) (l-1,r+1) (l−1,r+1)。计算方法为不断地向上更新 l , r l,r l,r，如果 l l l是左孩子则计入 l l l的兄弟结点，如果 r r r是右孩子则计入 r r r的兄弟结点，直到 l , r l,r l,r是兄弟结点。

int query(int n,int m){
    int sum=0;
    for(int l=n-1,r=m+1;l^r^1;l>>=1,r>>=1){//l^r^1!=0表示l和r不是兄弟结点
        if(!l&1) sum+=tree[l^1];
        if(r&1) sum+=tree[r^1];
    }
    return sum;
}