_JF_ • 2年前
某个zz辱骂管理无法上谷。
所以用这里来写学习笔记qwq
理论上还是一个复习笔记qwq,适合复习的选手看。
线段树,也就是一种二叉树。
本文均以加和举例。
显然如果是二叉树的话,我们查询左右节点的方式是:
int ls(int p)
{
return p<<1;
}
int rs(int p)
{
return p<<1|1;
}
然后我们考虑开一个 d 数组 来维护这个线段树,然后我们考虑节点封装。
通常是:
struct node
{
int ls,rs,sum;
// 根据实际情况决定
}
我们考虑用 d_p 表示当前节点编号为 p,左右端点为 [l,r] 的信息。
先考虑建树。
假设当前节点为 p,可以二分当前的区间去进行建树,要记得在回溯的时候上传信息,也就是 push_up 函数。
void push_up(int p)
{
d[p].sum=d[ls(p)].sum+d[rs(p)].sum;
//具体情况随实际
}
void build(int s,int t,int p)
{
if(s==t)
{
d[p]=a[s];
return ;
}
int mid=(l+r)>>1;
build(l,mid,p<<1),build(mid+1,r,p<<1|1);
push_up(p);
}
然后是考虑区间查询,(先不考虑懒标记)。
那就是把当前的区间 [l,r] 不断地二分,如果分到了当前的区间 [s,t] 正好在线段树中有确定的值的话,那就直接用就行,否则不断二分。
int getsum(int l,int r,int s,int t,int p)
{
if(l<=s&&t<=r)
return d[p];
int mid=(l+r)>>1;
return getsum(l,r,s,mid,ls(p))+getsum(l,r,mid+1,t,rs(p));
}
评论: