1, 线段树是一棵二叉搜索树, 它储存的是一个区间的信息.
2, 每个节点以结构体的方式存储, 结构体包含以下几个信息:
区间左端点, 右端点;(这两者必有)
这个区间要维护的信息(事实际情况而定, 数目不等).
3, 线段树的基本思想: 二分.
4, 线段树一般结构如图所示:
每个节点的左孩子区间范围为[l,mid], 右孩子为[mid+1,r]
线段树的基础操作主要有 5 个:
建树, 单点查询, 单点修改, 区间查询, 区间修改.
- (以下均为求和操作)
- struct node{
- int l,r,w;//l 左区间, r 右区间, w 区间和
- }xdtree[4*n];//n 个数
一, 建树
a, 对于二分到的每一个结点, 给它的左右端点确定范围.
b, 如果是叶子节点, 存储要维护的信息.
c, 状态合并.
!!:: 4 倍空间
不要漏了 return 语句
- void build(int l,int r,int k){//k 是根节点的下标
- xdtree[k].l=l;
- xdtree[k].r=r;
- if(l==r){
- cout<<xdtree[k].w;//n 个数的和
- return;
- }
- int m=(l+r)/2;
- build(l,m,2*k);
- build(m+1,r,2*k+1);
- xdtree[k].w=xdtree[2*k].w+xdtree[2*k+1].w;
- }
二, 单点查询
- void ask(int k){//k 一般为 1,x 是查询点
- int ans;
- if(xdtee[k].l==xdtree[k].r)
- ans=xdtree[k].w,return;
- int m=(xdtree[k].l + xdtree[k].r)/2;
- if(x<=m) ask(k*2) ;// 若目标靠左, 递归左儿子
- else ask(k*2+1);// 目标靠右. 递归右儿子
- }
三, 单点修改
第 x 个数加上 y
- void add(int k){
- if(xdtree[k].l==xdtree[k].r)
- xdtree[k].w+=y,return;
- int m=(xdtree[k].l+xdtree[k].r)/2;
- if(x<=m) add(k*2);
- else add(k*2+1);
- xdtree[k].w=xdtree[k].w+xdtree[k].w;// 更新包含 k 的节点
- }
四, 区间查询
查询 [ x , y ] 的值
mid=(l+r)/2
x<=mid , 即 查询区间全在, 当前区间的左子区间, 往左孩子走
y>mid 即 查询区间全在, 当前区间的右子区间, 往右孩子走
否则, 两个子区间都走
- void ask_(int k){
- if(xdtree[k].l>=x&&xdtree[k].r<=y)
- ans += xdtree[k].w,return;
- int m=(xdtree[k].l+xdtree[k].r)/2;
- if(x<=m) ask_(k*2);
- if(y>m) ask_(k*2+1);
- }
- #include<bits/stdc++.h>
- using namespace std;
- int n;
- struct node{
- int l,r,w;//l 左区间, r 右区间, w 区间和
- }xdtree[4*n];//n 个数
- void build(int l,int r,int k){//k 是根节点的下标
- xdtree[k].l=l;
- xdtree[k].r=r;
- if(l==r){
- cout<<xdtree[k].w;//n 个数的和
- return;
- }
- int m=(l+r)/2;
- build(l,m,2*k);
- build(m+1,r,2*k+1);
- xdtree[k].w=xdtree[2*k].w+xdtree[2*k+1].w;
- }
- void ask(int k){// 设 x 是查询点的下标
- int ans=0;
- if(xdtee[k].l==xdtree[k].r)
- ans=xdtree[k].w,return;
- int m=(xdtree[k].l + xdtree[k].r)/2;
- if(x<=m) ask(k*2) ;// 若目标靠左, 递归左儿子
- else ask(k*2+1);// 目标靠右. 递归右儿子
- }
- void add(int k){
- if(xdtree[k].l==xdtree[k].r)
- xdtree[k].w+=y,return;
- int m=(xdtree[k].l+xdtree[k].r)/2;
- if(x<=m) add(k*2);
- else add(k*2+1);
- xdtree[k].w=xdtree[k].w+xdtree[k].w;// 更新包含 k 的节点
- }
- void ask_(int k){
- if(xdtree[k].l>=x&&xdtree[k].r<=y)
- ans += xdtree[k].w,return;
- int m=(xdtree[k].l+xdtree[k].r)/2;
- if(x<=m) ask_(k*2);
- if(y>m) ask_(k*2+1);
- }
- int main(){
- return 0;
- }
线段树
来源: http://www.bubuko.com/infodetail-2964516.html