【科技】单点加区间求和能做到多快

· · 算法·理论

省流：单次操作 O(e^{W(\ln n)}) 在线区间可合并信息修改区间半群信息查询。

为什么标题是单点加？因为懒得下传标记。

十分的想把它命名成 Butterfly Tree，中文名称是蝶树，如果先前没有相似做法（本人没有查到）那么就这么命名吧。

本来在想更快的做法，不过再次迭代强如怪物拼尽全力无法战胜，如果有更快的做法可以告诉我。

不难发现，线段树是可以解决这个问题的。

不难发现，分块也是可以解决这个问题的。

不难发现，线段树是完全二叉树，分块是完全 \sqrt{n} 叉树。

不难发现，如果是完全 B 叉树的话，时间复杂度是 O(B+\log_Bn)。

不难发现，取 B^B=n 取到平衡。

那么这个 O(e^{W(\ln n)}) 是什么鬼？

事实上是 O(B)。

\begin{aligned}B^B=n&\to B\ln B=\ln n\\&\to \ln B\times e^{\ln B}=\ln n\\&\to W(\ln n)=\ln B\\&\to B=e^{W(\ln n)}\end{aligned}

但是感觉好像没优化多少，是个 O(\log^{1-\epsilon}n)。问题不大，优化了就好。

建议使用类 zkw 线段树来实现多层分块。

给个模板（树状数组 1）代码吧：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
int n,m,c[N];
void update(int u,int w){for(;u;u/=5)c[u]+=w;}
int query(int l,int r)
{
    int res=0;
    for(;l/5!=r/5;l/=5,r/=5)
    {
        while(l%5)res+=c[l++];
        while(r%5)res+=c[--r];
    }
    for(int i=l;i<r;i++)res+=c[i];
    return res;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=0,a;i<n;i++){cin>>a;update(n+i,a);}
    for(int i=1,op,x,y;i<=m;i++)
    {
        cin>>op>>x>>y;
        if(op==1)update(x+n-1,y);
        else cout<<query(x+n-1,y+n)<<'\n';
    }
}

其中 5 为 B，经手动枚举，这是使得 B+\log_Bn 最小的一个数。

可以注意到，确实肉眼可见的快了。