[蓝桥杯] 树状数组与线段树问题（C/C++）

文章目录

一、动态求连续区间和

1、1 题目描述

1、2 题解关键思路与解答

二、数星星

2、1 题目描述

2、2 题解关键思路与解答

三、数列区间最大值

3、1 题目描述

3、2 题解关键思路与解答

题目来源：《信息学奥赛一本通》,Acwing模板题

题目难度：简单

题目描述：给定 n 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b] 的连续和。

输入格式：

  第一行包含两个整数 n 和 m，分别表示数的个数和操作次数。

  第二行包含 n 个整数，表示完整数列。

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

  数列从 1 开始计数。

输出格式：

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

数据范围：

  1≤n≤100000,   1≤m≤100000，   1≤a≤b≤n,   数据保证在任何时候，数列中所有元素之和均在 int 范围内。

输入样例：

输出样例：

  我们知道求一段区间的和用前缀和数组会很方便，时间复杂度也很快。但是当修改数组的数据时，我们又要重新求前缀和数组，这样下来时间复杂的就较高了，为O（n*n）的级别的。这个时候我们就可以用到树状数组来求解。树状数组是一个一维数组，每个位置存储的数据是一段区间的和。以下为书抓鬼呢数组的模板：我们只需要记住树状数组有三个比较重要的函数，lowbit（找下一个要操作的数）、add（改变大小）、query（求区间和）。我们看代码：