目录
线段树
简介
- 线段树(一个二叉树)是一个非常重要的数据结构，利用分治的思想。可以用于维护一些满足结合律区间的信息，例如区间元素之和，区间异或和。
- 线段树可以实现O(logn)(需要Lazy tag,朴素版只允许单点修改和区间查询)的时间复杂度的区间修改和区间查询,与树状数组相比,它更具有通用性,但是常数略大。
节点
线段树由多个节点组成，每个节点包含以下信息
- 编号: O
- 管辖区间: [st,ed]
- 权值: 和/最值/异或和/(等满足性质数据)
加法线段树
前缀和在查询与加法交替出现时复杂度很高,不适用
此处可使用树状数组,但是线段树可拓展性更强
因为线段树一定是二叉树,所以一般利用二叉树编号性质构造整棵树.对于编号为x的节点,左儿子为2x,右儿子为2x+1.所以不需要记录左右儿子,但是也使得需要开四倍n的数组才能存下整棵树,一般以1号节点为根.
树的大小为1时为叶节点,叶节点组成原数组
线段树每次操作从根节点开始,每个节点的管辖区间可以由根算出来s
1. 准备变量
#define int long long
const int N = 2e5+10;
int a[N];//原数组
int n;//原数组大小
int t[N << 2];//开四倍空间，t[x]表示节点x所表示的区间元素大小
2. 上拉操作
purhup(上拉操作)是所有线段树所有操作都需要用到的工具函数,是用儿子信息来更新自己的信息.
void pushup(int o)
{
t[o] = t[o<<1] + t[0<<1 | 1];//可能不是加法
}
3. 建树
建树采用分治思想, 分别将左右子树建立,然后利用pushup来更新当前节点.
void bulidTree(int s = 1,int e = n,int o = 1)
{
if(s == e)
{
t[o] = a[s];
return ;
}
int mid = s + e >> 1;
bulidTree(s,mid,o<<1),bulidTree(mid+1,e,o<<1 | 1);
pushup(o);
}
4. 懒标记
懒标记(lazytag)用于表示某个节点尚未更新给子节点的值, 懒标记是保证线段树的区间修改和区间查询的复杂度正确性的关键.
int lz[N<<2];
//lz[o]表示: 节点o还有lazy[o]这么大的一个数字,还没有加给左右儿子.
当lz[o] == 0,说明当前节点的左右儿子都已经被更新，得到了正确的值，使用懒标记必须配合下放操作
5. 下放操作
pushdown(下放操作)需要三个参数, 分别是当前的操作区间([st,ed])和节点编号(O).
void pushdown(int s,int e,int o)
{
if(!lz[o]) return ;//如果lz[o] == 0,无需下放
int mid = s + 1 >> 1,ls = 0<<!,rs = o<<1 | 1;//ls,rs为左右儿子编号
t[ls] += lz[o] * (mid - s + 1);//可改为updata()
t[rs] += lz[o] * (e-mid);
//每个t(区间和)都需要乘上一个区间长度.
lz[ls] += lz[o],lz[rs] += lz[o];//标记也要下放
lz[o] = 0;//lz下放完毕
}
6. 区间修改
将区间[l,r]中的数字都加上x,采用递归形式,当走到了目标区域内,就将对应的t[o]和lz[o]做出修改.
此函数是线段树精髓
void add(int l,int r,int x,int s = 1,int e = n,int o = 1)
{
if(l <= s && e <= r)
{
//当前操作区间已经完全进入目标区间,应该直接被修改并且打算lz标记,不再向下
t[o] += (e-s+1)*x;
lz[o] += x;
return;
}
pushdown(e,s,o);//向下走前,必须下放
int mid = s + e >> 1;
if(mid >= l) add(l,r,x,s,mid,o<<1);//判断是否需要往左走
if(mid + 1 <= r) add(l,r,x,mid+1,e,o<<1 | 1);//判断是否需要往右走
pushup(o);//递归回来,上拉
}
updata
void updata(int s,int e,int o,int x)
{
t[o] += (e-s+1)*x;
lz[o] += x;
}
异或线段树
只需要修改"pushup"和"updata"
pushup
将"+"改为"^"即可
void pushup(int o)
{
t[o] = t[o<<1] ^ t[o<<1 | 1];
}
updata
void updata(int s,int e,int o,int x)
{
t[o] ^= ((e - s + 1)&1) ? x : 0;// 奇数才异或x
//因为偶数次异或等同于未操作
lz[o] ^= x;
}
最值线段树
updata
将区间[s,e],节点o加上x
void updata(int s,int e,int o,int x)
{
tmax[o] += x,tmin[o] += x;
lz[o] += x;
}
pushup
void pushup(int o)
{
tmax[o] = max(tmax[o<<1],tmax[o<<1 | 1]);
tmin[o] = min(tmin[o<<1],tmin[o<<1 | 1]);
lz[o] += x;
}