线段树学习笔记

线段树的构造
void build(Node* cur,int l,int r)
{
cur->Left=l;//区间左端点
cur->Right=r;//区间右端点
if (l+1<r)//如果不是初等区间，那么继续递归构建
{
cur->LeftChild=new Node;
cur->rightChild=new Node;
build(cur->LeftChild,l,(l+r)>>1);
build(cur->rightChild,(l+r)>>1,r);
}
else
cur->leftChild=cur->rightChild=NULL;
}

//线段树的查询
int query(Node* cur,int l,int r)
{
if (l<=cur->Left&&cur->Right<=r)//如果查询区间覆盖了当前节点
return cur->sum;
else
{
int ans=0;
if (l<(cur->Left+cur->Right)/2)//如果查询到了当前节点的左孩子
ans+=query(cur->LeftChild,l,r);
if (r>(cur->Left+cur->Right)/2)
ans+=query(cur->rightChild,l,r);
return ans;
}
}
//线段树的延迟修改
void change(Node* cur,int x,int delta)
{
if (cur->Right+1==cur->Right)//找到了要修改的位置
cur->sum+=delta;
else {
if (x<(cur->Left+cur->Right)/2)
change(cur->LeftChild,x,delta);
if (x>(cur->Left+cur->Right)/2)
change(cur->RightChild,x,delta);
cur->sum=cur->LeftChild->sum+cur->RightChild->sum;
//递归结束后需要用子树的信息来更新当前节点
}
}
//线段树的查询
void change(Node* cur,int l,int r,int delta)
{
if (l<=cur->Left&&cur->Right<=r) ///如果被修改区间覆盖了当前节点
{
cur->sum+=delta*(cur->Right-cur->Left);//更新sum
cur->delta+=delta; //累计修改
}
else {
if (cur->delta!=0)//如果有待下传的累计
update(cur);
if (l<(cur->Left+cur->Right)/2)
change(cur->LeftChild,l,r,delta);
if (r>(cur->Left+cur->Right)/2)
change(cur->RightChild,l,r,delta);
cur->sum=cur->LeftChild+cur->RightChild;
}
}
其中，延迟信息向下传的方法update可以这么写：
void update(Node* cur)
{
cur->LeftChild->sum+=cur->delta*(cur->LeftChild->Right)
}

//查询过程也需要进行相应的修改
int query(Node* cur,int l,int r)
{
if (l<=cur->Left&&cur->Right<=r)
return cur->sum;
else {
if (cur->delta!=0)
update(cur);
int ans=0;
if (l<(cur->Left+cur->Right)/2)
ans+=query(cur->LeftChild,l,r);
if (r>(cur->Left+cur->Right)/2)
ans+=query(cur->RightChild,l,r);
return ans;
}
}