线段树节点数据结构：

class SegmentTree{
    int l,r;   //每个区间的左右端点
    int sum;   //区间数据
    //其他附加信息
}

建树

以完全二叉树建树，可以使用父子二倍标记法，子节点下标为父节点下标值的两倍。

//递归建树
//p:当前父节点，sak为节点数组
void build(int p,int l,int r){
    sak[p].l=l;sak[p].r=r;
    if(l==r){
        sak[p].sum=a[l];
        return;
    }
    int mid = (l+r)/2;
    //依次建立左右子树
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    sak[p].sum = sak[2*p].sum+sak[2*p+1].sum;
}

单点修改

每次操作都是从根节点开始遍历，递归找到需要修改的节点。

//p:当前节点    x:目标节点      val:修改值    
void change(int p,int x,int val){
    if(sak[p].l==sak[p].r){
        sak[p].sum = val;
        return;
    }
    int mid = (l+r)/2;
    if(x <= mid) change(p*2,x,val);
    else change(p*2+1,x,val);
    sak[p].sum = sak[p*2].sum + sak[p*2+1].sum;
}

区间查询

1. 若当前节点所表示的区间已经被询问区间所完全覆盖，则立即回溯，并传回该点的信息。
2. 若当前节点的左儿子所表示的区间已经被询问区间所完全覆盖，就递归访问它的左儿子。
3. 若当前节点的右儿子所表示的区间已经被询问区间所完全覆盖，就递归访问它的右儿子。

int ask(int p,int l,int r){
    if(l <= sak[p].l && r >= sak[p].r) return sak[p].sum;
    int val = 0 ;
    int mid = (sak[p].l + sak[p].r)/2;
    if(l<=mid) val+=ask(2*p,l,r);
    if(r>mid) val+=ask(2*p+1,l,r);
    return val;
}

---