『笔记』重口味(zkw)线段树

· · 个人记录

重口味线段树

标签： 数据结构

前言

对于以前写的xxs线段树笔记，补充一份简洁易懂并且跑得飞快的代码

普通线段树和 \text{zkw} 线段树的结构是差不多的，但是一个是用递归实现，而另一个则用简单的循环即可实现它，好调试并且速度比递归版的线段树快上接近一倍（麻麻再也不用担心卡常了），但是依旧是优缺点的，\text{zkw} 线段树只能用于单种运算，不能处理运算优先级的问题，就比如（加法+乘法），所以说两种都要学习才可

zkw线段树的题目整理

功能

一、单点修改+区间单点查询

不需差分，建树 \text{O(nlgn)} ,修改 \text{O(lgn)} ,区间查询 \text{O(lgn)} ,单点查询 \text{O(1)}

二、区间修改+\text{RMQ} 查询

差分建树 \text{O(nlgn)} ,修改 \text{O(lgn)} ,查询 \text{O(lgn)}

三、区间查询最大值小值

zkw线段树实现方法

对比一下递归版的线段树代码，可以发现操作都是从顶部向下在返回的，那么 \text{zkw} 线段树是从底部向上的（肉眼可见的两倍关系）

递归版的线段树可以不是满二叉树，\text{zkw} 线段树的二叉树一定为满二叉树（空间换时间了），找到叶子节点回溯上去就完事了

树的建立

上图简单理解一下

找一找二叉树上的规律（学过线段树的都很会吧）

1、儿子节点右移一位到达父亲节点

2、父亲节点左移一位和左移一位 +1 分别是他的左儿子和右儿子

3、第 n 层有 2^{n-1} 个节点

4、最后一层有多少个节点，下标的定义域就是多少

有了这四个显而易见的规律，那么就开始建树把

const int N=1e5+9;
int tree[N<<2];
int n,m=1;

四倍空间是必须的，其中 m 表示的是非叶子节点的个数， n 表示要用的序列长度，其实也就是要用的叶子节点的个数，

void build()
{
    while(m<=n) m<<=1；
    for(int i=1;i<=n;i++)//需要注意的是，序列是从二叉树最后一层从左到右第二个节点开始存的,主要是为了方便。
        a[i+m]=read();
}

首先简单处理子节点，把序列的初始值赋进去

对于如何处理父亲节点，这个可以维护三种操作

for(int i=m-1;i;i--) 
    tree[i]=tree[i<<1]+tree[i<<1|1];//区间求和

for(int i=m-1;i;i--) 
    tree[i]=min(tree[i<<1]+tree[i<<1|1];//区间最小值

for(int i=m-1;i;i--) 
    tree[i]=max(tree[i<<1]+tree[i<<1|1];//区间最大值

另外一种建树方式就是差分建树，可以应用于单点查询和区间修改+区间查询中

void build()
{
    while(m<=n) m>>=1;
    for(int i=1;i<=n;i++)
        tree[i+m]=read();
    for(int i=m-1;i;i--)//差分建树
    {
        tree[i]=min(tree[i<<1],tree[i<<1|1]);
        tree[i<<1]-=tree[i];
        tree[i<<1|1]-=tree[i];
    }
}

修改操作

单点修改

void change(int x,int val)//修改下标为 x 的值
{
    tree[m+x]+=val;//如果是加减法
    tree[m+x]=val;//如果是直接修改值
    while(x>>=1)//向上更新节点的值
        tree[x]=tree[x<<1]+tree[x<<1|1];
}

查询操作

单点查询

其实有两种操作可以实现，一种是正常建树，对于询问直接\text{O(1)} 求输出 \text{tree[i+m]}就完事了

另一种就是较为牛逼的差分了,我们可以把查询范围从 [l,r] 变成 (l-1,r+1) 进行查询，如果当前的 l 指向了左孩子，那么就把右孩子的值加上，如果当前的 r 是右孩子的，那么就把他的左孩子加上。

void query(int l,int r)
{
    int ret=0;
    for(l=m-1,r=m+1;l^r^1;l>>=1,r>>=1)
    {
        if(~l&1) ret+=tree[l^1];
        if(r&1) ret+=tree[r^1];
    }
    printf("%d\n",ret);
}

以 \langle 1,2,3,4,5\rangle 为例建出树来其实就是这个样子：

一目了然可以看到差分的牛逼之处

区间查询

非常正常的建树就行了

void query(int l,int r)
{
    int ret=0;
    for(l+=m-1,r+=m+1；l^r^1;l>>=1,r>>=1)
    {
        if(~l&1) ret+=tree[l^1];
        if(r&1) ret+=tree[r^1];
    }
    printf("%d\n",ret);
}

代码

例题