专栏首页数据结构与算法10:Challenge 3(树状数组直接修改)

10:Challenge 3(树状数组直接修改)

总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述

给一个长为N的数列,有M次操作,每次操作是以下两种之一:

(1)修改数列中的一个数

(2)求数列中某连续一段的和

输入第一行两个正整数N和M。

第二行N个整数表示这个数列。

接下来M行,每行开头是一个字符,若该字符为'M',则表示一个修改操作,接下来两个整数x和y,表示把x位置的值修改为y;若该字符为'Q',则表示一个询问操作,接下来两个整数x和y,表示求[x,y]这段区间的和。输出对每一个询问操作单独输出一行,表示答案。样例输入

5 3
1 2 3 4 5
Q 1 5
M 2 7
Q 1 5

样例输出

15
20

提示1<=N<=10^5,1<=M<=10^5,输入保证合法,且所有整数及答案可用带符号32位整型存储。考虑树状数组肯定是没有什么疑问的,但是这里不是加减,而是直接修改,然而直接修改会爆零,原因自己yy一下就知道。所以说,我们每次改的时候,去加上要加的数和当前的数的差,然后再把当前的数改成将要改的数

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int MAXN=100001;
 6 int a[MAXN];
 7 int tree[MAXN];
 8 int n,m;
 9 void read(int &n)
10 {
11     char c='+';int x=0;bool flag=0;
12     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
13     while(c>='0'&&c<='9')
14     x=(x<<1)+(x<<3)+c-48,c=getchar();
15     flag==1?n=-x:n=x;
16 }
17 int lb(int p)
18 {
19     return (p)&(-p);
20 }
21 void add(int pos,int v)
22 {
23     int p=pos;
24     while(p<=n)
25     {
26         tree[p]+=v;
27         p+=lb(p);
28     }
29 }
30 int sum(int pos)
31 {
32     int ans=0;
33     int p=pos;
34     while(p)
35     {
36         ans+=tree[p];
37         p-=lb(p);
38     }
39     return ans;
40 }
41 int main() 
42 {
43     read(n);read(m);
44     for(int i=1;i<=n;i++)
45     {
46         int p;
47         read(p);
48         a[i]=p;
49         add(i,p);
50     }
51     for(int i=1;i<=m;i++)
52     {
53         char c;int x,y;
54         cin>>c;read(x);read(y);
55         if(c=='Q')
56             printf("%d\n",sum(y)-sum(x-1));
57         else
58         {
59             add(x,y-a[x]);
60             a[x]=y;
61         }
62             
63     }
64     return 0;
65 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 关于scanf与cin哪个快的问题

    一开始入c++的时候成天跑cin,cout 直到有一天用cin,cout超时 才知道scanf比cin快的多 但是后来又听说加了ios::sync_with_s...

    attack
  • HDU 1573 X问题

    Problem Description 求在小于等于N的正整数中有多少个X满足: Input 输入数据的第一行为一个正整数T,表示有T组测试数据。每组测...

    attack
  • 洛谷P4197 Peaks(Kruskal重构树 主席树)

    考虑把Kruskal重构树建出来,重构树上每个新的节点代表的是边权,同时用倍增数组维护出跳2^i步后能走到的值最大的节点

    attack
  • 2016天梯模拟赛 进阶题解

    L2-005 集合相似度 题目链接: https://www.patest.cn/contests/gplt/L2-005 题目的意思是要求两个集合的交集中...

    ShenduCC
  • 一遍记住Java常用的八种排序算法与代码实现

    (如果每次比较都交换,那么就是交换排序;如果每次比较完一个循环再交换,就是简单选择排序。)

    田维常
  • HDU 1573 X问题

    Problem Description 求在小于等于N的正整数中有多少个X满足: Input 输入数据的第一行为一个正整数T,表示有T组测试数据。每组测...

    attack
  • Day2上午解题报告

    预计分数:100+0+60=160 实际分数:100+0+60=160 mmpT1数据错了。。。 T1遭遇 题目描述 你是能看到第一题的 friends呢。 —...

    attack
  • LeetCode 第 210 场周赛 解题报告

    那么在遍历过程中,栈中元素数量的最大值即为答案。栈中的(可以理解为还没遍历到匹配的),即那些嵌套的(。

    ACM算法日常
  • 洛谷P4180 [Beijing2010组队]次小生成树Tree

    题目描述 小C最近学了很多最小生成树的算法,Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时,小P又来泼小C冷水了。小P说,让小C求出一个无...

    attack
  • 图论--拓扑排序--判断一个图能否被拓扑排序

    拓扑排序的实现条件,以及结合应用场景,我们都能得到拓扑排序适用于DAG图(Directed Acyclic Graph简称DAG)有向无环图, 根据关系我们能得...

    风骨散人Chiam

扫码关注云+社区

领取腾讯云代金券