线段树是一种二叉树，它的每一个节点代表一个区间[a，b]，它的叶节点代表单位区间[a,a]，即点a。
对一个非叶节点，设它的编号为x，区间为[a，b]，那么它的左儿子的编号就是（2*x）,区间是[a,(a+b)/2]；它的右儿子的编号是（2*x+1）,区间是[(a+b)/2+1,b]
线段树的实现通常分为以下几个函数：
build()//建立线段树
update()//更新线段树（区间更新或者单点更新）
query()//查询(区间和、区间最值)
pushdown()//向下延时更新
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
int sum[N],a[N],lazy[N];
void build(int l,int r,int rt)
{
if(l==r){
sum[rt]=a[l];
return;
}
int mid=(l+r)/2;
build(l,mid,rt*2);//先左儿子后又儿子
build(mid+1,r,rt*2+1);
sum[rt]=sum[rt*2]+sum[rt*2+1];//当前区间和等于左儿子和右儿子区间和
}
void pushdown(int l,int r,int rt){
if(lazy[rt]){
lazy[rt*2]+=lazy[rt];//向下延时更新
lazy[rt*2+1]+=lazy[rt];
lazy[rt]=0;
sum[rt*2]+=l*lazy[rt*2];//下面的儿子区间和也加
sum[rt*2+1]+=r*lazy[rt*2+1];
}
}
int query(int l1,int r1,int l,int r,int rt){
if(l1<=l&&r1>=r){
return sum[rt];
}
int mid=(l+r)/2;
int ret=0;
pushdown(mid-l+1,r-mid,rt);//更新后
if(l1<=mid){
ret+=query(l1,r1,l,mid,rt*2);
}
if(r1>mid){
ret+=query(l1,r1,mid+1,r,rt*2+1);
}
return ret;
}
void update(int p,int v,int l,int r,int rt)//单点增加或减少
{
if(l==r)
{
sum[rt]+=v;
return;
}
int mid=(l+r)/2;
if(p<=mid){
update(p,v,l,mid,rt*2);
}
if(p>mid){
update(p,v,mid+1,r,rt*2+1);
}
sum[rt]=sum[rt*2]+sum[rt*2+1];
}
void update2(int l1,int r1,int v,int l,int r,int rt)//区间增加或减少
{
if(l1<=l&&r1>=r){
sum[rt]+=v*(r-l+1);
lazy[rt]+=v;//通过延时函数实现
return;
}
int mid=(l+r)/2;
if(l1<=mid){
update2(l1,r1,v,l,mid,rt*2);
}
if(r1>mid){
update2(l1,r1,v,mid+1,r,rt*2+1);
}
sum[rt]=sum[rt*2]+sum[rt*2+1];
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
build(1,n,1);
}
return 0;
}
注意：1.线段树要开四倍大小空间（证明可见本页备注链接）
https://blog.csdn.net/gl486546/article/details/78243098
2.建树复杂度为o(nlogn)每次更新、询问的复杂度均为o(logn)
（最坏情况是从根节点一直更新到叶子节点）