呵呵呵呵呵呵呵呵呵呵Today我们要讲树状数组。先从问题引入主题(其中100%的数据保证 “1 ≤ n, m ≤ 500,000”)乍一眼看上去使用前缀和做的先写一下暴力代码。#include bits/stdc.h // 万恶之源inf 1( inf) using namespace std; // 万恶之源inf 2( inf) int n, m; // n个数字, m次询问 int a[500005]; // a数组 int s[500005]; // 前缀和数组 int main() { cin n m; for (int i 1; i n; i) { // 输入n个数 cin a[i]; s[i] s[i - 1] a[i]; // 前缀和初始化 } while (m--) { int op, x, y; // 如果op是1, 那么a[x] y, 否则输出a[x] ~ a[y]的数值之和 cin op x y; if (op 1) { for (int i x; i n; i) s[i] y; // 如果一个点变了, 那么后面所有前缀和数组的值都会变 } else { cout s[y] - s[x - 1] \n; // 输出a[x] ~ a[y]的和 } } } // 完结, 不撒花(T_T) // 因为这个代码是错误的为什么是错误的呢来看一下时间复杂度最坏x1循环1~n又有m次时间复杂度就是O(nm)。前缀和慢就慢在这个增加上面因此我们今天的重头戏上场了——什么是树状数组核心用处高效单点修改 区间前缀和查询时间复杂度是 O(logn)。优点代码极短、常数小时间快。缺点扩展性弱只能解决这类问题。树状数组实现相比于普通的数组前缀和树状数组管辖的区域相对小一点。x前缀和树状数组管辖区间之和111[1,1]222[1,2]331[3,3]444[1,4]551[5,5]662[5,6]771[7,7]888[1,8]管辖区域特定要求管辖区应为最后一个出现的1代表的十进制数。如 6 - 110 管辖(10)的十进制数也就是2个数范围是5~6再如 16 - 10000 管辖(10000)的十进制数也就是16个数范围是1~16不同的数有着不同的管辖范围。那该如何解决呢令下标为xval为x -x则c[x]的管辖区域为[x - val ~ x]。那为什么不是别的偏偏是x -xlet us remind what is 二进制吧十进制数值类型32 位编码8 位分节16原码00000000 00000000 00000000 0001000016反码00000000 00000000 00000000 0001000016补码00000000 00000000 00000000 00010000-16原码10000000 00000000 00000000 00010000-16反码11111111 11111111 11111111 11101111-16补码11111111 11111111 11111111 1111000040原码00000000 00000000 00000000 0010100040反码00000000 00000000 00000000 0010100040补码00000000 00000000 00000000 00101000-40原码10000000 00000000 00000000 00101000-40反码11111111 11111111 11111111 11010111-40补码11111111 11111111 11111111 11011000计算机运算是利用补码实现的。来计算16-1600000000 00000000 00000000 0001000011111111 11111111 11111111 11110000↓00000000 00000000 00000000 00010000||既然要完成单点加求区间和树状数组都可解决时间复杂度是,且x常数很小。代码稍微处理一下即可#include bits/stdc.h // 万恶之源 inf 3( inf) using namespace std; // 万恶之源 inf 4( inf) int n, m; int a[500005], c[500005]; // a原数组c树状数组 // 单点加a[x] y void add(int x, int y) { // 既然加了一个点那么所有的管辖区都要变 while (x n) { c[x] y; x x -x; // lowbit(x) x -x, 因为c运算都是按补码完成的 } } // 查询前缀和1~x 的和 int query(int x) { int ans 0; while (x 0) { ans c[x]; // 求出x所有管辖区域的c[x]之和 x - x -x; } return ans; } int main(){ cin n m; for (int i 1; i n; i) { cin a[i]; add(i, a[i]); // 初始化树状数组 } while (m--) { int op, x, y; cin op x y; if (op 1) { add(x, y); // 操作1a[x] y } else { cout query(y) - query(x - 1) \n; // 操作2查询[x,y]和 } } } // 完结撒花~ // *★,°*:.☆(▽)/$:*.°★* 。