算法1
(树状数组)
时间复杂度
参考文献
C++ 代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
const int N = 100010;
int a[N],tr[N];
int n,m;
int lowbit(int x)
{
return x & -x;
}
void add(int x,int y)
{
for(int i = x;i<=n;i += lowbit(i)) tr[i] +=y;
}
int query(int x)
{
int res = 0;
for(int i = x;i>0;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);
}
}
线段树做法
//线段树版本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010;
int w[N];
struct Node
{
int l;
int r;
int sum;
}tr[N* 4];
int n,m;
void pushup(int u)
{
tr[u].sum = tr[u * 2].sum + tr[u * 2+1].sum;
}
void build(int u,int l, int r)
{
if(l == r) tr[u] = {l,r,w[r]};
else
{
tr[u] = {l,r};
int mid = (l+r)/2;
build(u*2,l,mid);
build(u*2+1,mid+1,r);
pushup(u);
}
}
int query(int u,int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
int mid =( tr[u].l + tr[u].r ) /2;
int sum = 0;
if(l <= mid) sum += query(u*2,l,r);
if(r >= mid+1) sum += query(u*2+1,l,r);
return sum;
}
void modify(int u,int x,int v)
{
if(tr[u].l == tr[u].r ) tr[u].sum += v;
else
{
int mid = (tr[u].l + tr[u].r)/2;
if(x <= mid ) modify(u*2,x,v);
else modify(u*2+1,x,v);
pushup(u);
}
}
int main()
{
cin>>n>>m;
for(int i = 1;i<=n;i++) cin>>w[i];
build(1,1,n);
while(m--)
{
int k,a,b;
cin>>k>>a>>b;
if(k == 0) printf("%d\n",query(1,a,b));
else modify(1,a,b);
}
}