本文共 517 字，大约阅读时间需要 1 分钟。

前言

树状数组的话很早以前就学过了。。

一开始停留在改点求段上面。。 然后发现差分之后他还可以改段求点。。 其实在以前，我以为除了代码长度，这玩意被线段树完爆了。。 后来才发现有常数这个东西QAQ 于是昨天在~~参考~~Claris的代码的时候发现，这玩意居然可以改段求段。。

做法

设原数组第i位的值为a[i],设d[i]=a[i]-a[i-1]

求a的前x位求和，就是这样子的:

$$\sum^{x}_{i=1}a[i]=\sum^{x}_{i=1}\sum^{i}_{j=1}d[j]$$ 我们不妨可以变形一下，考虑每一个d对答案的贡献： $$\sum^{x}_{i=1}a[i]=\sum^{x}_{i=1}(x-i+1)*d[i]$$ 我们可以拆项: $$\sum^{x}_{i=1}a[i]=\sum^{x}_{i=1}x*d[i]-\sum^{x}_{i=1}(i-1)*d[i]$$ 很明显，前后两个东西我们是可以分开维护的。。 于是我们就可以开两个树状数组，一个维护d的前缀和，在查询的时候再乘上x。 另外一个维护（i-1）*d[i] 然后查询的时候就两个查一下，做个差就可以了

CODE：

在写这篇博客的时候在makedown上面写的，应该能编译

#include
   
    int main(){    printf("自己上网找，我这里没有");    return 0;}