洛谷P2068 统计和

题目描述

给定一个长度为\(n（n \leq 100000）\)，初始值都为\(0\)的序列，\(x(x \leq 10000)\)次的修改某些位置上的数字，每次加上一个数，然后提出\(y (y \leq 10000)\)个问题，求每段区间的和。时间限制\(1\)秒。

输入输出格式

输入格式：

第一行\(1\)个数，表示序列的长度\(n\)

第二行\(1\)个数，表示操作的次数\(w\)

后面依次是\(w\)行，分别表示加入和询问操作

其中，加入用\(x\)表示，询问用\(y\)表示

\(x\)的格式为"\(x\) \(a\) \(b\)" 表示在序列\(a\)的位置加上\(b\)

\(y\)的格式为"\(y\) \(a\) \(b\)" 表示询问\(a\)到\(b\)区间的加和

输出格式：

每行一个数，分别是每次询问的结果

输入输出样例

输入样例#1：

输出样例#1：

8

17

思路：一道(线段树&树状数组)的(单点修改&区间查询)的板子题，不用过多解释……

代码：

#include<cstdio>

#include<algorithm>

#define maxn 100007

#define lb(x) x&(-x)

using namespace std;

int n,m,a[maxn];

char s[2];

inline void add(int x, int w) {

  while(x<=n) {

    a[x]+=w;

    x+=lb(x);

  }

}

inline int csum(int x) {

  int ans=0;

  while(x) {

    ans+=a[x];

    x-=lb(x);

  }

  return ans;

}

int main() {

  scanf("%d%d",&n,&m);

  for(int i=1,l,r;i<=m;++i) {

    scanf("%s%d%d",s,&l,&r);

    if(s[0]=='x') add(l,r);

    else printf("%d\n",csum(r)-csum(l-1));

  }

  return 0;

}

巴特西

洛谷P2068 统计和

题目描述

输入输出格式

输入输出样例

最新文章

热门文章