线段树一

这里会从我对线段树最开始的理解一点一点的讲下去,

这篇的查询问题均为区间查询, 修改问题均为单点修改

先做一个假设,假设区间长度为$length = 2^k$k为正整数,只有在我大段证明口胡的时候这样方便一点,其实区别不大
对于一个数列来说,如果只查询区间信息,那样就可以很简单的用前缀和来维护前缀和数组sum,就可以得到很简单的证明下面的那个式子
单个前缀和
sum[r] - sum[l - 1] = $ \sum_{i = l}^r a[i] $
但是如果在操作中会用到修改操作那样若像得到正确答案则需要维护sum数组
显然若是修改到第一个点时,修改的代价将会是$O(length)$,当然查询的代价依然还是$O(1)$
但显然若是修改次数很多,那样时间肯定会T的飞起
因此我们可以重新考虑一下前缀和,
所以我们可以考虑将前缀和数组一分为二
那样我们就可以得到这样的结果
一分为二的前缀和
对这个图片分析,就能简单的发现单点修改的最坏情况下维护sum数组可以少维护一半
只不过查询将会变成2次
也就是说,我们若要分很多次,如果变成了这个样子
单层分最多
但是这样显然是有很大的问题,因为现在的情况虽说修改的话最需要修改对应的结点信息,也就是说修改操作一次,最多需要修改3个最少可以修改两个,不过我们可以显然的发现一个小小的优化,对于此事黄色的每一块,我们可以直接让他们维护所覆盖的原数组的区间和,到这里也就是说每格黄色的将是维护两格黑色的区间和,也就说我们需要用$ \frac {length}{2}$个空间维护原来的空间,这样显然会比用$length$个空间去维护常数更小
当然上面那一段说的问题只是一个小问题,毕竟现在我们可以发现的一个最大的问题就是,!!!没有用!!!
就是上面的操作看起来没有任何用,因为不过是查询,还是修改的只是让他变得复杂了点,虽然变复杂,而且看起来没有任何用,但是我们可以从这里发现一个关键的性质,就是问题的规模变小了,原来需要在$length$长度的序列进行操作,现在我们通过这个复杂的变化将查询的操作变成了在长度为$\frac{length}{2}$的数组在加上原数组最多两个元素规模的查询操作,而且修改的也仅仅只是增加了一次变成了两次
也就是说我们可以通过一次这样的操作来将查询的问题规模缩小一半在加最多两次(为什么两次可以自行理解,我这里就不做详细的解释了,自己思考会对线段树的很多操作的认知都会有很大的提升),然后修改操作增加一次
因此我若进行最大限度的上述操作($log_2length$次)我就会得到这样的结构
线段树
于是乎看到第一眼就很容易发现,这就是一颗满二叉树(因为最初保证了$length$是2的次幂,否则不一定是一颗完全二叉树),因次就很容易发现这是一颗只有叶子结点存储信息的一颗树,而非叶子结点存储的信息是只是帮助我们快速的维护和查询叶子的信息,
既然出现了树的结构,那样我们就可以定义一下他的每个结点

struct node
{
    int l, r, val;
    //我们可以这样定义对于当前结点所包含的区间信息为, 区间[l, r]的和为val
}tr[length * 4]; // *4是为了符合可以完整的建立起来这棵树,而且不会出现数组越界之类的情况
//这个length可以不为2^k的倍数

不过我们在实现前先分析一下这样写的代价
首先进行一次单点修改,根据区间和的信息我们将会修改$log_2length$个结点
其次进行一次区间查询,根据上图的结构我们很容易发现,最多需要遍历$2log_2length$个结点
首先单点修改肯定没有疑问,因为对于每个结点信息都会有上面的$log_2length-1$个结点将其信息存储下来,并且也需要修改本身的结点,
对于区间查询首先我们考虑如果一层出现访问三个结点,首先我们可以知道的一点是,这三个结点最多只会隔开一个空,所以至少有两个的父亲是一样的,所以就可以在他父亲哪里停下来,至于为什么中间是隔开一个空的可以仔细看一下上图
这样我们的线段树就已经定义好了,接下来我们要做的就是建立好这棵树

void build(int k, int l, int r) // 当前建立的结点是区间l到r的,是编号为k的结点
{
    tr[k].l = l;
    tr[k].r = r;
    if(l = r)
    {
        tr[k].val = a[l]; // 第k个结点对应的叶子结点储存的值
        return ; // 结束递归
    }
    int mid = (l + r) / 2;
    build(k * 2, l, mid); 
    // 先建立并填写完整左子树的信息,至于为什么是k * 2之类的可以先复习一下二叉树的知识点
    build(k * 2 + 1, mid + 1, r);
    //同上
    tr[k].val = tr[k * 2].val + tr[k * 2 + 1].val;
    //递归的维护信息
}//只有先递归到叶子结点维护好叶子结点信息之后在一层一层的往上依次维护就可以简单的维护完成
void change(int k, int l, int r, int val) // 这里的操作是单点加,其他操作都大同小异
{
    // 其实只需要a[k].l == a[k].r就行,单点修改的l和r本身就相等
    if(l <= a[k].l && a[k].r <= r) 
    {
        tr[k].val += val;
        return ; //结束递归
    }
    int mid = (a[k].l + a[k].r) / 2; // 这里是a[k].l和a[k].r不是l和r
    if(l <= mid) change(k * 2, l, r, val);
    else change(k * 2 + 1, l, r, val);
    //单点操作非左即右
    tr[k].val = tr[k * 2].val + tr[k * 2 + 1].val; // 这句话不能忘写
}
// 这个函数就不写为什么可以这样写了
int query(int k, int l, int r)
{
    if(l <= a[k].l && a[k].r <= r)
    {
        return a[k].val;
    }
    int mid = (a[k].l + a[k].r) / 2;
    int ans = 0;
    if(l <= mid) ans += query(k * 2, l, r);
    if(r >  mid) ans += query(k * 2 + 1, l, r);
    return ans;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注