一般先建立结构体，要开4倍,还有a数组，存一开始的数据
struct tree
{
int l,r,ans;
}tr[N<<2];
int a[N];
//建立一棵树
void built_tree(int x,int y,int i)
{
tr[i].l =x;
tr[i].r =y;
if(x==y) tr[i].ans=a[x];
else
{
int mid=(x+y)>>1;
built_tree(x,mid,i<<1);//左树
built_tree(mid+1,y,i<<1|1);//右树
tr[i].ans=tr[i<<1].ans+tr[i<<1|1].ans; //和递归返回 求区间和的
//如果求最大值 tr[i],ans=min(tr[i<<1].ans,tr[i<<1|1].ans);
}
}
//修改点的值
void update_tree(int q,int val,int i)
{
if(tr[i].l ==q && tr[i].r ==q)
tr[i].ans+=val;
else
{
int mid=(tr[i].l+tr[i].r)>>1;
if(q<=mid)
update_tree(q,val,i<<1);
else
update_tree(q,val,i<<1|1);
tr[i].ans=tr[i<<1].ans+tr[i<<1|1].ans;
}
}
//查询答案
int query_tree(int x,int y,int i)
{
if(tr[i].l >=x&&tr[i].r <=y) return tr[i].ans;
else
{
int mid=(tr[i].l +tr[i].r )>>1;
if(x>mid)
return query_tree(x,y,i<<1|1);
else if(y<=mid)
return query_tree(x,y,i<<1);
else
return query_tree(x,y,i<<1)+query_tree(x,y,i<<1|1);
}
}
修改区间的值，查询
//重点详解：
//void pushdown(int);//下放惰性标记
//此处标记指的是惰性标记，实际上是让子节点暂时处于
//不更新状态等到用到的时候在做更新而区间加时要把和
//那个区间有关的区间全部价值，不然不配合输出
//超时了就要优化。
//你想啊，虽然x~y区间要增加一个值，难道这个区间就一
//定要用吗？
//如果区间值增加了但后来没有询问，我们一开始为什么
//要增加呢？
//正如背古文，如果考试不考，我们为什么要背呢？
//所以lazy思想就怎么产生了。
//lazy，就是懒嘛，就是先不被古文，等到考试要考了再
//去背嘛；
//先不增加区间，等到询问时在去增加嘛；
//我们可以搞一个add数组，专门把编号为num的区间要加
//的值记录下来
//如果要用了，再给线段树num加上v[num]的值，再把
//lazy[num]
//传给左右两棵树;然后lazy清零
ll a[N];//存储最初的数据
struct node{
int l,r;
ll sum,lazy;//记录该条线段出现的次数
}tree[N];//保存每个点左右端点和极值
//数组模拟，空间开到4倍防止访问越界
void build_tree(int l,int r,int i){//构造线段树
tree[i].l=l;
tree[i].r=r;
if(l==r){//找到叶子节点并且赋值
tree[i].sum=a[l];
tree[i].lazy =0;
return;
}
int mid=(l+r)>>1;
build_tree(l,mid,i<<1);//左子树
build_tree(mid+1,r,(i<<1)|1);//右子树
tree[i].sum=tree[i<<1].sum+tree[(i<<1)+1].sum;
//回溯维护区间和
}
void pushdown(int i){//下放惰性标记
int lc=i<<1, rc=(i<<1)+1;
tree[lc].sum+=(tree[lc].r-tree[lc].l+1)*tree[i].lazy;
tree[rc].sum+=(tree[rc].r-tree[rc].l+1)*tree[i].lazy;
tree[lc].lazy+=tree[i].lazy;
tree[rc].lazy+=tree[i].lazy ;
tree[i].lazy=0;//此处下放标记
}
void update_tree(int x,int y,ll k,int i){//区间修改
int lc=i<<1;
int rc=(i<<1)|1;
if(tree[i].l>y || tree[i].r<x){
return;//如果此区间完全无关
}
if(x<=tree[i].l && tree[i].r<=y){
tree[i].sum+=(tree[i].r-tree[i].l+1)*k;
tree[i].lazy+=k;//存放惰性标记
} //如果此处是完全有关区间
else{
if(tree[i].lazy){
pushdown(i);//下放惰性标记
}
update_tree(x,y,k,lc);
update_tree(x,y,k,rc);
tree[i].sum=tree[lc].sum+tree[rc].sum;
}//二分添加
}
ll query_tree(int x,int y,int i){
int lc=i<<1;
int rc=(i<<1)+1;
if(x<=tree[i].l && tree[i].r<=y){
return tree[i].sum;
}
if(tree[i].l>y || tree[i].r<x){
return 0;
}
//完全在左子树中or右子树
if(tree[i].lazy){
pushdown(i);//下放惰性标记
}
return query_tree(x,y,lc)+query_tree(x,y,rc);
//目标区间左右都有分布
}