线段树

概念：线段树将数组区间递归二分，每个结点维护一个区间信息，适用于区间求和、最值等可合并操作，并可扩展懒标记处理区间修改。

关键步骤

建树时叶子存数组值、父结点合并儿子；查询遇到完全覆盖直接返回，部分覆盖则递归两侧。单点修改沿根到叶的路径更新。

vector<long long> tr,a;
void build(int p,int l,int r){
    if(l==r){ tr[p]=a[l]; return; }
    int m=(l+r)/2; build(p*2,l,m); build(p*2+1,m+1,r);
    tr[p]=tr[p*2]+tr[p*2+1];
}
long long query(int p,int l,int r,int L,int R){
    if(L<=l && r<=R) return tr[p];
    int m=(l+r)/2; long long ans=0;
    if(L<=m) ans+=query(p*2,l,m,L,R);
    if(R>m) ans+=query(p*2+1,m+1,r,L,R); return ans;
}

复杂度

建树 O(n)，单点更新与区间查询 O(log n)，空间 O(n)（常开 4n）。区间更新需将懒标记下推后再访问子结点。