题目描述
blablabla
样例
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int a[N], tr[N];
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 query(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++ ) add(i, a[i]);
while (m -- )
{
int k, x, y;
scanf("%d%d%d", &k, &x, &y);
if (k == 0) printf("%d\n", query(y) - query(x - 1));
else add(x, y);
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla