没有用的帖子。

某个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));
}