线段树

标签: 算法学习

线段树能把区间上的任意一条长度为 L 的线段都分成不超过 2log L条线段。
因此对于查询或修改某个长度为 L的区间,我们只要在分解 出来的线段上操作,然后在合并这几个区间信息即可。
所以对于一般的操作,单次时间复杂度都是 O(log n)
在这里插入图片描述

  • 每个节点维护一个闭区间[l,r] (l<=r)的信息。
  • 根节点表示[1,n]的信息。
  • 如果l==r就是叶子结点。
  • 如果了l<r就是内部节点,他有两个子节点[l,(l+r)/2],[(l+r)/2+1,r].
    用1表示根节点。
    下标为x的左子节点下标为2x,右子节点下标为2x+1.
    用sum[x]表示x代表的区间所有数的和。
    对于叶子节点,l==r,sum[x]=a[r];
//线段树的链表存储
struct node{
	int left,right,value;
	node *lchild,*rchild;
};
/*
left和right表示节点区间
value维护这个区间的信息,比如区间和等;
每个节点同时维护两个孩子的指针。
坏处就是指针要动态申请,由于寻址不连续,所以效率不高。
*/
//数组存储
/*
数组存储也有一点不好,因为线段树并是真正的完全二叉。
最后一层可能很空。且节点的数量以达到 2n 个。
因此维护长度为 n的序列,用数组存线段树话最好要开 到 4*n的
*/
void build(int l,int r,int x)
{
	if(l==r)//叶子节点
	{
		sum[x]=a[r];
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,x*2);
	build(mid+1,r,x*2+1);
	update(x);//更新信息
}
void update(int x)//更新信息
{
	sum[x]=sum[x*2]+sum[x*2+1];
}
/*
查询的过程也是自顶向下。
假设询问区间是 [A, B] ,现在所的节点表示区间为 [l, r]
• 如果 A <= l<= r<= B  ,那么直接返回当前节点的 sum , 不用递归下去。
• 否则,我们需要判断不递归到两个子节点上询问。
线段树的查询
假设询问区间是 [A, B] ,现在所的节点表示区间为 [l, r]
• 计算 mid = (l + r) / 2 mid = (l + r) / 2 ,左子节点的区间为 [l, mid] , 右子节点的区间为 [mid+1, r]. [mid+1, r].
• 如果 A<= mid ,即询问区间与左子节点有重合需要递归 到左子节点。
• 如果 B >= mid + B >= mid +1,即询问区间与右子节点有重合,需要 递归到右子节点。
• 递
*/
int query(int A,int B,int l,int r,int x)//线段树查询
{
	if(A<=l&&r<=B)
		return sum[x];
	int mid=(l+r)>>2,ans=0;
	if(A<=mid)
		ans+=query(A,B,l,mid,x*2);
	if(B>mid)
		ans+=query(A,B,mid+1,r,x*2+1);
	return ans;
}
int change(int pos,int v,int l,int r,int x)//对单个元素的修改,单个元素位于叶子节点
{
	if(l==r)//找到需要修改的叶子节点
	{
		sum[x]=v;
		return;
	}
	int mid=(l+r)>>1;
	if(pos<==mid)//pos在左子节点
		change(pos,v,l,mid,x*2);
	else
		change(pos,v,mid+1,r,x*2+1);
	update(x);//sum值发生改变
}
原文链接:加载失败,请重新获取