一个简单的整数问题2
-
维护区间的时候和上一题的思想类似,也是用树状数组维护一个差分数组。但是在需要区间和的时候则和上一题的思想不太相同。在上一题中,想要求出 $a[x]$ ,只需要求出差分数组中的 $\sum_{i=1}^{x}{b[i]}$ 。但是在这一题中,如果想要求出 $\sum_{i=l}^{r}a[i]$ 则需要求出 $\sum_{i=l}^{r}\sum_{j=1}^{i}b[j]$ 。需要进行两层循环。如果只是暴力按照之前的做法来做的话时间复杂度 $O(nmlogn)$ 是一定会超时的。
-
$\sum_{i=l}^{r}\sum_{j=1}^{i}b[j]$ 可以看成
$$ \begin{equation} %开始数学环境 \left( %左括号 \begin{array}{ccc} %该矩阵一共3列,每一列都居中放置 b1\\ %第一行元素 b1 & b2 \\ %第二行元素 b1 & b2 & b3\\ b1 & b2 & b3 & b4\\ … \end{array} \right) %右括号 \end{equation} $$
这样一个矩阵。比如 $a[1]\sim{a[4]}$ 的区间和的矩阵如上图所示。但是这个矩阵不容易用代码求出来,,因此可以将其进行如下的填充
$$ \begin{equation} %开始数学环境 \left( %左括号 \begin{array}{ccc} %该矩阵一共3列,每一列都居中放置 b1 & \textcolor{red}{b2} & \textcolor{red}{b3} & \textcolor{red}{b4} \\ %第一行元素 b1 & b2 & \textcolor{red}{b3} & \textcolor{red}{b4} \\ %第二行元素 b1 & b2 & b3 & \textcolor{red}{b4} \\ b1 & b2 & b3 & b4\\ … \end{array} \right) %右括号 \end{equation} $$
这一个矩阵中每个元素的和就很好求得了。在求得总和之后再减去标红的元素的总和,就可以求得真正的 $a[l]\sim{a[r]}$ 的和。其公式如下
$\sum_{i=l}^{r}\sum_{j=1}^{i}b[j]=\sum_{i=1}^{x}(x-i+1)\times{b[i]}=(x+1)\sum_{i=1}^x{b[i]}-\sum_{i=1}^{x}i\times{b[i]}$
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 100010;
int n, m;
ll tr1[N], tr2[N]; // tr1是b[i]的前缀和,tr2是b[i] * i的前缀和
ll a[N];
int lowbit(int x)
{
return x & -x;
}
void add(ll tr[], int x, ll v)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}
ll sum(ll tr[], int x)
{
ll res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
ll prefix_sum(int x)
{
return sum(tr1, x) * (x + 1) - sum(tr2, x);
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ )
{
ll b = a[i] - a[i - 1];
add(tr1, i, b);
add(tr2, i, (ll)b * i);
}
while (m -- )
{
char op[2];
cin >> op;
int l, r, d;
cin >> l >> r;
if (*op == 'Q')
{
cout << prefix_sum(r) - prefix_sum(l - 1) << endl;
}
else
{
cin >> d;
add(tr1, l, d), add(tr2, l, l * d);
add(tr1, r + 1, -d), add(tr2, r + 1, (r + 1) * -d);
}
}
return 0;
}
。。在acwing写latex好像有点问题,在typora上面是正常显示的