个人对于珂朵莉树的新想法

· · 算法·理论

前言

本人只是一个刚学 OI 不久的蒟蒻，文中内容仅仅是分享一下个人的观点，如果各位 dalao 有不认同或想要指正的地方欢迎来评论区友好交流 （不喜勿喷）

正文

在使用了几次 ODT 后，我也发现了它的一大缺点，就是特别容易被数据卡掉 （像是说废话）

本来想着去看看怎么优化，但我太弱了，看不懂其他 dalao 的高级优化方式。

于是乎，在本人深（机）入（缘）研（巧）究（合）之下，我发现了一种实现较为简单的优化方式。

优化思路

可以知道，珂朵莉树能被卡其实是因为被切成了很多小的碎区间，几乎与暴力没有区别。所以我就想着是不是可以舍弃掉一些无意义的分割？

那哪些分割是无意义的呢？显然，对于单次的区间查询，普通的 ODT 也会对区间进行分割，但这似乎根本没有必要？

以维护区间和为例，在查询时，我们似乎只需要知道左右两端点所对应的区间就行了，得到对应区间的迭代器后只需要对两端进行特判，只加 l 到左端点区间的最右端，和右端点区间的最左端到 r，中间部分正常求和即可，复杂度也与正常 ODT 没有区别，这样似乎可以省去分割的步骤，是不是也就降低了程序的整体复杂度？

其实本人想到这里是有些小激动的，因为目前似乎没看到有人提出类似的方法。

（也有可能是思维太简单了，各位 dalao 根本不屑于提出）

后续部分都是围绕这个想法展开，各位 dalao 要是不感兴趣可以不用浪费时间了

实践过程

想再多也不如实践试试，于是乎本蒟蒻就去重写了几个之前尝试过的例题。

（以下图片来自例题 P4690）

这是第一次写的代码的结果，只写了一棵普普通通的珂朵莉树。

加上了本人提出的优化方案后……

（虽然结局没有改变，但复杂度似乎确实更优了些？）

优化的效果大家也都看到了，有是有，但在询问数量正常的题里效果不是特别明显，不过考虑到代码实现极其简单，还是给大家提供一个新思路吧。

代码实现

其他的代码与普通珂朵莉树没啥区别，唯一不同的是，在进行查询操作时，我们不使用 split 函数，而是额外定义一个仅仅取出当前点位所对应的迭代器的函数

IT xun(int pos)//IT已宏定义为指针类型
{
    IT it=tree.lower_bound(node(pos));
    if (it != tree.end() and it->l == pos)
    {
        return it;
    }
    it--;
    return it;
}

有了它之后，我们再对查询函数也稍做修改（还是以区间求和为例子）

int ask2(int l,int r)//优化后
{

    IT itr=xun(r),itl=xun(l);
    IT fz=itr;//记录右端点所在的区间
    itr++;
    if (itl == fz)//记得特判一下 l，r 处于同一区间
    {
        return (r-l+1)*itl->v;
    }
    LL sum=0;
    for (IT it = itl;it != itr;it++)
    {
        if (it == itl)
        {
            sum+=(itl->r - l +1)*itl->v;

        }
        else if (it == fz)
        {
            sum+=(r- fz->l + 1)*it->v;

        }
        else
        {
            sum+=(it->r - it->l +1)*it->v;

        }

     }
     return sum;
}

注意如果使用这种方式的话在查询右端点所在区间时就不能再 +1 了，而是要等查询完毕后给迭代器手动加一位。

然后，我们此时维护的珂朵莉树在查询时就不会再去分割区间了，并且查询的复杂度对比普通珂朵莉树也无显著变化，整体上复杂度下降的程度似乎还算可观。

总结

这种优化仅仅是我个人突发奇想想到的，（可能各位 dalao 在此之前早已有过类似的思路）

感觉在应对题目询问次数较多时效果会好一些，不过代码实现反正这么简单，就跟快读一样都加上也不会吃亏。

感谢各位 dalao 能耐心把本文看完，如果有什么其他思路或者更好的建议可以在评论区留下，我看到会及时回复的。

（都看到这里了，求个赞不过分吧 QWQ）