AcWing 242. 一个简单的整数问题
原题链接
简单
一个简单的整数问题
- 这道题说要多次给一段数字都加上一个数。把数列中 $l\sim{r}$ 的元素每个都加上 $d$ 。很容易想到这里可以用到差分的方法。而在求某一个数的值的时候,需要将差分数组的 $1\sim n$ 的数全都加起来。如果用普通的差分数组的话这个操作的事件复杂度是 $O(n)$ 。因此很容易想到要用树状数组将时间复杂度优化为 $O(logn)$ 。在初始化整个树状数组的时候的时间复杂度是 $O(n)$ ,操作的事件复杂度是 $0(logn)$ ,总时间复杂度是 $max(O(n), O(mlogn))$ 。
#include <iostream>
const int N = 100010;
using namespace std;
int tr[N], a[N];
int n, m;
int lowbit(int x)
{
return x & -x;
}
void add(int x, int v)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}
int sum(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ ) add(i, a[i] - a[i - 1]);
while (m -- )
{
char op[2];
cin >> op;
if (*op == 'Q')
{
int t;
cin >> t;
cout << sum(t) << endl;
}
else
{
int l, r, d;
cin >> l >> r >> d;
add(l, d), add(r + 1, -d);
}
}
return 0;
}