P2068 统计和

短命女 2021-11-26 07:31 188阅读 0赞

## 题目描述 ##

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

## 输入输出格式 ##

输入格式：

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

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

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

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

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

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

输出格式：

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

## 输入输出样例 ##

输入样例\#1：  复制

5
    4
    x 3 8
    y 1 3
    x 4 9
    y 3 4

输出样例\#1：  复制

8
    17

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    #include<queue>
    using namespace std;
    int n,m,xx,yy;
    char a;
    int c[100000],tree[100000];
    int lowbit(int t){
        return t&(-t);
    }
    int getsum(int x){
        int ans=0;
        for(int i=x;i;i-=lowbit(i)){
            ans+=c[i];
        }
        return ans;
    }
    void add(int x,int y){
        for(int i=x;i<=n;i+=lowbit(i)){
            c[i]+=y;
        }
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%d",&tree[i]);
            add(i,tree[i]);
        }
        while(m--){
            cin>>a;
            scanf("%d %d",&xx,&yy);
            if(a=='x'){add(xx,yy);}
            if(a=='y'){
                printf("%d\n",getsum(yy)-getsum(xx-1));
            }
        }
        return 0;
    }

终于，能较为熟练的使用树状数组了。

orz YG  &  YYR  .

转载于:https://www.cnblogs.com/xiongchongwen/p/11148796.html

发表评论取消回复

表情：

评论列表（有 0 条评论，188人围观）

还没有评论，来说两句吧...

相关阅读

相关 hdu 2068（错排+组合）水题

hdu 2068（错排+组合）水题 [题目链接][Link 1] 以前做过一次，开始没做出来，这次做的话，感觉还是比较水的，就是错排加上组合公式就可以了错排公式：f

小鱼儿/ 2023年06月09日 10:04/ 0 赞/ 5 阅读

相关 P2234 [HNOI2002]营业额统计

[题目链接][Link 1] 平衡树练手题，我们看它这个数列是动态插入的，所以自然而然就会想到用平衡树来维护。平衡树Splay推荐大家看[这篇博客][Link 2] 其实差

约定不等于承诺〃/ 2023年06月04日 07:59/ 0 赞/ 52 阅读

相关 P1567 统计天数（模拟）

1. 问题描述：炎热的夏日，KC 非常的不爽。他宁可忍受北极的寒冷，也不愿忍受厦门的夏天。最近，他开始研究天气的变化。他希望用研究的结果预测未来的天气。经历千辛万苦，他收集

以你之姓@/ 2022年09月11日 13:15/ 0 赞/ 137 阅读

相关洛谷P1308 统计单词数

题目描述一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。现在，请你编程实现这一功能，具体要求

阳光穿透心脏的1/2处/ 2022年06月01日 10:38/ 0 赞/ 217 阅读

相关洛谷P1567 统计天数

题目背景统计天数题目描述炎热的夏日，KC非常的不爽。他宁可忍受北极的寒冷，也不愿忍受厦门的夏天。最近，他开始研究天气的变化。他希望用研究的结果预测未来的天气

缺乏、安全感/ 2022年06月01日 09:26/ 0 赞/ 225 阅读

相关洛谷P1026 统计单词个数

题目描述给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1<k<=40)

柔情只为你懂/ 2022年05月27日 13:45/ 0 赞/ 246 阅读

相关【数理统计】神奇的P值

AB Test 工作中经常会通过AB Test帮助做产品决策，简单说就是为产品制作两个（A/B）或多个（A/B/C/...）版本，在同一时间维度，分别让不同组的用户群随机

桃扇骨/ 2021年12月22日 06:59/ 0 赞/ 414 阅读

相关 P2590 [ZJOI2008]树的统计

题目描述一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作： I. CHANGE u t : 把结点u的

迷南。/ 2021年11月26日 07:36/ 0 赞/ 202 阅读

相关 P2068 统计和

题目描述给定一个长度为n（n<=100000），初始值都为0的序列，x(x<=10000)次的修改某些位置上的数字，每次加上一个数，然后提出y (y<=10000)个问

短命女/ 2021年11月26日 07:31/ 0 赞/ 189 阅读

相关【洛谷 2068】统计和

题目描述给定一个长度为n（n<=100000），初始值都为0的序列，x(x<=10000)次的修改某些位置上的数字，每次加上一个数，然后提出y (y<=10000)个问

你的名字/ 2021年10月19日 11:28/ 0 赞/ 297 阅读