令原数组为({a_n})，差分数组({d_i=a_i-a_{i-1}})
显然(a_x=sum_{i=1}^x d[i])
我们现在要求(sum_{i=1}^x a_i)
把每个(a_i)都按上面的形式表示，就有(sum_{i=1}^x a_i=sum_{i=1}^x d_i(x-i+1)=(x+1)sum_{i=1}^x d_i-sum_{i=1}^x id_i)
于是开2个树状数组维护({d_i})和({id_i})即可
令原数组为({a_n})，差分数组({d_i=a_i-a_{i-1}})
显然(a_x=sum_{i=1}^x d[i])
我们现在要求(sum_{i=1}^x a_i)
把每个(a_i)都按上面的形式表示，就有(sum_{i=1}^x a_i=sum_{i=1}^x d_i(x-i+1)=(x+1)sum_{i=1}^x d_i-sum_{i=1}^x id_i)
于是开2个树状数组维护({d_i})和({id_i})即可