[mw_shl_code=c,true]#include <cstdio>
struct Tree
{
int l, r;
long long sum;
} tr[1024000];
int a[1024000];
void Build_Tree ( int x , int y , int i )
{
tr.l = x;
tr.r = y;
if( x == y ) tr.sum = a[x] ; //找到叶子节点,赋值
else
{
int mid = (tr.l + tr.r ) / 2 ;
Build_Tree ( x , mid , i * 2); //左子树
Build_Tree ( mid + 1 , y , i * 2 + 1); //右子树
tr.sum = tr[i * 2].sum + tr[i * 2 + 1].sum; //回溯维护区间和
}
}
long long Query_Tree ( int q , int w , int i )
{
if ( q <= tr.l && w >= tr.r ) return tr.sum; //当前结点的区间完全被目标区间包含
else
{
long long mid = (tr.l + tr.r) / 2;
if( q > mid ) //完全在左儿子
{
return Query_Tree ( q , w , i * 2 + 1);
}
else if (w <= mid ) //完全在右儿子
{
return Query_Tree ( q , w , i * 2);
}
else //目标区间在左右都有分布
{
return Query_Tree ( q , w , i * 2) + Query_Tree ( q , w , i * 2 + 1 );
}
}
}
void Update_Tree ( int q , int val , int i )
{
if(tr.l == q && tr.r == q) //找到需要修改的叶子节点
{
tr.sum += val ; //更新当前结点
}
else //当前结点是非叶子结点
{
long long mid = (tr.l + tr.r ) / 2 ; //取中间
if ( q <= mid ) //目标节点在左儿子中
{
Update_Tree ( q , val , i * 2 );
}
else if( q > mid ) //目标节点在右儿子中
{
Update_Tree ( q , val , i * 2 + 1 );
}
tr.sum = tr[i*2].sum + tr[i*2+1].sum; //回溯
}
}
int main ( )
{
int N, M, q, val, l, r;
scanf("%d", &N);
for ( int i = 1 ; i <= N ; i++ )
scanf("%d", &a);
Build_Tree ( 1 , N , 1);
scanf("%d",&M);
while (M--)
{
int op ;
scanf("%d",&op);
if ( op == 1 )
{
scanf("%d%d", &q, &val);
Update_Tree ( q , val , 1);
}
else
{
scanf("%d%d", &l, &r);
printf("%lld\n", Query_Tree ( l , r, 1 ));
}
}
return 0 ;
}
[/mw_shl_code]
|