前言
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第十三讲：树状数组与线段树【例题】
本篇博客所包含习题有：
👊动态求连续区间和
👊数星星
👊数列区间最大值
树状数组与线段树【习题】见博客：蓝桥杯第十三讲–树状数组与线段树【习题】
注： 蓝桥杯对于树状数组与线段树的考察十分的基础简单，且历年只考察过两道题目，读者不需要了解其原理，只需要背诵模板学会调用即可。如果想要知道具体实现方式，见博客：树状数组，线段树（一），线段树（二） 【尚未更新】
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
动态求连续区间和
题目要求
题目描述：
给定 n 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列[a,b] 的连续和。
输入格式：
输出格式：
输出若干行数字，表示 k = 0 时，对应的子数列 [a,b] 的连续和。
数据范围：
数据保证在任何时候，数列中所有元素之和均在int 范围内。
输入样例：
10 5 1 2 3 4 5 6 7 8 9 10 1 1 5 0 1 3 0 4 8 1 7 5 0 4 8
输出样例：
11 30 35
思路分析
本题用 树状数组 以及 线段树 两种方法去写，同时介绍模板
树状数组
使用树状数组会让时间复杂度变为：O(logn)树状数组作用有两个：
- 让某个位置上的数加上一个数（单点修改）
- 求一个前缀和（区间查询）
当然，树状数组还有其他功能，但是对于蓝桥杯而言，只需要掌握以上两种即可
树状数组虽然是一维的，但是我们可以把它理解为是二维的，类似树的结构，如下图所示：
这里有几个需要注意的点：
以上就是对树状数组的一些定义说明，读者 不需要 知道为什么这么定义以及其中细节，感兴趣的可以看博客：树状数组【尚未更新】，里面会有讲解。
下面介绍树状数组的几个基本函数：
int lowbit(int x) { return x & -x; } void add(int x, int v) // 往 x 的位置加上一个数字 v { for (int i = x; i <= n; i += lowbit(i)) tr[i] += v; } int query(int x) // 求 [1, x] 原数组的前缀和 { int res = 0; for (int i = x; i; i -= lowbit(i)) res += tr[i]; return res; }
上述代码需要：背背背！！！
代码(树状数组)
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 1000010; int n, m; int a[N], tr[N]; int lowbit(int x) { return x & -x; } void add(int x, int v) { for (int i = x; i <= n; i += lowbit(i)) tr[i] += v; } int query(int x) { int res = 0; for (int i = x; i; i -= lowbit(i)) res += tr[i]; return res; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); for (int i = 1; i <= n; i ++ ) add(i, a[i]); while(m -- ) { int k, x, y; scanf("%d%d%d", &k, &x, &y); if (k == 0) printf("%d\n", query(y) - query(x - 1)); else add(x, y); } return 0; }
线段树
使用树状数组会让时间复杂度变为：O(logn)，线段树的作用特别之多，包含树状数组的所有功能并且有很多额外的功能，但是代码相较与树状数组而言比较冗长。
线段树可以简单的理解成一个二叉树：
即线段树是对一段的数组，每次均分为两份，一直均分直到不能均分，红线代表的是求和的过程。
原理不进行讲解，读者 不需要 知道为什么这么定义以及其中细节，感兴趣的可以看博客：线段树（一），线段树（二）【尚未更新】，里面会有讲解。
下面介绍线段树的几个函数：
struct Node { int l, r; // 涵盖范围，如上图中的蓝色字体就是l，r的取值 int sum; }tr[4 * N]; // 需要开题目要求的4倍大小，不需要知道其原理 void pushup(int u) // 动态维护线段树 { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; } void build(int u, int l, int r) // 建一个线段树，u为根，l和r代表两个子树的涵盖范围 { if (l == r) tr[u] = {l, r, w[l]}; else { tr[u] = {l, r}; int mid = l + r >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); pushup(u); } } int query(int u, int l, int r) // 查询操作，求[l, r]的和，可以换为别的，核心是递归 { if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum; int mid = tr[u].l + tr[u].r >> 1; int sum = 0; if (l <= mid) sum = query(u << 1, l, r); if (r > mid) sum += query(u << 1 | 1, l, r); return sum; } void modify(int u, int x, int v)// 修改操作，把x的位置的值加上一个v，可以换为别的，核心是递归 { if (tr[u].l == tr[u].r) tr[u].sum += v; else { int mid = tr[u].l + tr[u].r >> 1; if (x <= mid) modify(u << 1, x, v); else modify(u << 1 | 1, x, v); pushup(u); } }
代码(线段树)
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 100010; int n, m; int w[N]; struct Node { int l, r; int sum; }tr[4 * N]; void pushup(int u) { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; } void build(int u, int l, int r) { if (l == r) tr[u] = {l, r, w[l]}; else { tr[u] = {l, r}; int mid = l + r >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); pushup(u); } } int query(int u, int l, int r) { if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum; int mid = tr[u].l + tr[u].r >> 1; int sum = 0; if (l <= mid) sum = query(u << 1, l, r); if (r > mid) sum += query(u << 1 | 1, l, r); return sum; } void modify(int u, int x, int v) { if (tr[u].l == tr[u].r) tr[u].sum += v; else { int mid = tr[u].l + tr[u].r >> 1; if (x <= mid) modify(u << 1, x, v); else modify(u << 1 | 1, x, v); pushup(u); } } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]); build(1, 1, n); int k, a, b; while (m -- ) { scanf("%d%d%d", &k, &a, &b); if (k == 0) printf("%d\n", query(1, a, b)); else modify(1, a, b); } return 0; }
