树状数组——在高阶前缀和上的应用

大佬教程收集整理的这篇文章主要介绍了树状数组——在高阶前缀和上的应用，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

HDU中超第五场打完后补题，被一个高阶前缀和折磨了两天 记录一下想法

树状数组——高阶前缀和

首先强化一下概念：树状数组的基本（根本）操作是单点修改，单点查询前缀和

通过对前缀和做小学减法我们做到了区间查询

现在要求对 (a)​​ 数组做单点修改，查询 (a)​​ 数组的二维前缀和

设 (b,C) 两数组分别为一阶、二阶前缀和

这样就将一个二阶前缀和问题转化成了两个一阶前缀和问题

用两个树状数组，分别处理 (a_i)​​​ ，({(i-1)a_i})​​ 这两个序列即可

struct BitTree{//4行树状数组
    ll t[2*maxn];
    ll lb(int X) {return x&-x;}
    void add(int p, ll ad){for(int i=p;i<=n;i+=lb(i)) t[i]+=ad;}
    ll sum(int p){ return p?t[p] + sum(p-lb(p)):0;}
};

struct BitTree2{//二阶前缀和的树状数组
    BitTree bt1, bt2;
    void add(int p, ll ad){
        bt1.add(p, ad);
        bt2.add(p, ad * (p-1));
    }
    ll sum(int p){
        return bt1.sum(p) * p - bt2.sum(p);
    }
};

练习（模板题）

线段树最基础的模板题，区间修改区间查询，可以用二阶前缀和的树状数组做

具体而言，建立差分数组 (d)​ ，区间修改可以改为在 (d)​ 上的单点修改，那么区间查询就相当于查询 (d)​ 的二阶前缀和

BitTree2 bt;
ll d[maxn], n, m;

void solve(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> d[i];
        bt.add(i, d[i]);
        bt.add(i+1, -d[i]);
    }
    for(int i=1;i<=m;i++){
        int opt,x,y,k;
        cin >> opt >> x >> y;
        if(opt == 1){
            cin >> k;
            bt.add(x, k);
            bt.add(y+1, -k);
        }else{
            cout << bt.sum(y) - bt.sum(x-1) << 'n';
        }
    }
}

更高阶呢？

以三阶前缀和为例

推方程的时候，对于一般项 (frac{(2+k-i)*(1+k-i)}{2}a_i)​​，要注意把 (k) 和 (i) ​分开，目的是使某个(f(i)a_i) 形式的东西独立出来，方便单独用树状数组维护。

这里的过程是：

由此也成功转化成三个一阶前缀和问题

如果继续推下去，会发现 (n) 个树状数组就可以解决 (n) 阶前缀和问题

练习题（比赛原题）

三阶前缀和

题解见自己写的 2021暑假 HDU中超 第五场 1009

大佬总结

以上是大佬教程为你收集整理的树状数组——在高阶前缀和上的应用全部内容，希望文章能够帮你解决树状数组——在高阶前缀和上的应用所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。