M - 秋实大哥与线段树
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
“学习本无底，前进莫徬徨。” 秋实大哥对一旁玩手机的学弟说道。
秋实大哥是一个爱学习的人，今天他刚刚学习了线段树这个数据结构。
为了检验自己的掌握程度，秋实大哥给自己出了一个题，同时邀请大家一起来作。
秋实大哥的题目要求你维护一个序列，支持两种操作：一种是修改某一个元素的值；一种是询问一段区间的和。
Input
第一行包含一个整数n，表示序列的长度。
接下来一行包含n个整数ai，表示序列初始的元素。
接下来一行包含一个整数m，表示操作数。
接下来m行，每行是以下两种操作之一：
1 x v : 表示将第x个元素的值改为v
2 l r : 表示询问[l,r]这个区间的元素和
1≤n，m，v，ai≤100000，1≤l≤r≤n。
Output
对于每一个2 l r操作，输出一个整数占一行，表示对应的答案。
Sample input and output
| Sample Input | Sample Output |
|---|---|
3 |
3 |
解题报告
本题...显然没有什么特别的技巧，直接上线段树即可解决，唯一注意的就是使用long long.
#include <iostream>
#include <cstring> typedef long long ll;
using namespace std;
const int maxn = 5e5 + ;
ll tree[maxn]; void updata(int pos,int v,int o,int l,int r)
{
if (l == r)
{
tree[o] = v;
return;
}
int mid = l + (r-l)/;
if (pos <= mid)
updata(pos,v,*o,l,mid);
else
updata(pos,v,*o+,mid+,r);
tree[o] = tree[*o] + tree[*o+];
} ll query(int ql,int qr,int o,int l,int r)
{
if (ql <= l && r <= qr)
return tree[o];
ll res = ;
int mid = l + (r-l) / ;
if (ql <= mid)
res += query(ql,qr,*o,l,mid);
if (qr > mid)
res += query(ql,qr,*o+,mid+,r);
return res;
} int main(int argc,char *argv[])
{
int n,m;
memset(tree,,sizeof(tree));
scanf("%d",&n);
for(int i = ; i <= n ; ++ i)
{
int temp;
scanf("%d",&temp);
updata(i,temp,,,n);
}
scanf("%d",&m);
while(m--)
{
int i,j,k;
scanf("%d%d%d",&i,&j,&k);
if (i == )
updata(j,k,,,n);
else
{
ll ans = query(j,k,,,n);
printf("%lld\n",ans);
}
}
return ;
}