题目描述

给定n个数列，规定有两种操作，一是修改某个元素，二是求子数列[a,b]的连续和。数列的元素个数最多是10万个，询问操作最多10万次。

输入

第一行2高整数n，m（n表示输入n个数，m表示有m个操作）。保证1≤n,m≤10^6

第二行输入n个数列。

接下来m行，每行有三个数k，a，b（k=2，表示求子数列[a,b]的和；k=1，表示第a个数加b）。

输出

输出若干行数字，表示k=2时，对应的子数列[a,b]的连续和。

保证1≤a≤b≤n，|b|≤10^6

样例

输入数据 1

3 2
1 2 3
1 2 0
2 1 3

输出数据 1

6

题解如下：
 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5e4+5;
ll n,m,c1[MAXN],c2[MAXN];
ll lowbit(ll i){
return i&(-i);
}
void u1(ll x,ll value){
for(ll i=x;i<=n;i+=lowbit(i))
c1[i]+=value;
}
ll find1(ll x){
ll res=0;
for(ll i=x;i;i-=lowbit(i))
res+=c1[i];
return res;
}
void u2(ll x,ll value){
for(ll i=x;i<=n;i+=lowbit(i))
c2[i]+=value;
}
ll find2(ll x){
ll res=0;
for(ll i=x;i;i-=lowbit(i))
res+=c2[i];
return res;
}
int main(){
scanf("%lld%lld",&n,&m);
for(ll i=1,k,l,r;i<=m;i++){
scanf("%lld%lld%lld",&k,&l,&r);
if(k==1){
u1(l,1);
u2(r,1);
}
else
printf("%lldn",find1(r)-find2(l-1));
}
}

最后

以上就是拼搏小甜瓜为你收集整理的凡人升天传2——「一本通 4.1 例 1」数列操作题目描述样例的全部内容，希望文章能够帮你解决凡人升天传2——「一本通 4.1 例 1」数列操作题目描述样例所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。