企业网站建设参考文献,沈阳妇科医生哪个好,短链接在线生成器,生产建设兵团第三师政务网站第五十六章 树状数组一、前缀和的缺陷二、树状数组1、作用2、算法分析3、算法实现#xff08;1#xff09;lowbits()#xff08;2#xff09;插入#xff08;3#xff09;查询三、例题1、问题题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示2、代码一、前缀和…
第五十六章 树状数组一、前缀和的缺陷二、树状数组1、作用2、算法分析3、算法实现1lowbits()2插入3查询三、例题1、问题题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示2、代码一、前缀和的缺陷
我们在很久之前介绍过前缀和算法。
我们先来分析一下前缀和算法的优点和缺陷。
这个算法的优点在于能够在O(1)O(1)O(1)的时间复杂度内算出某段区间的和。但是这个过程的前提是我们没有去修改原数组。也就是说如果我们在后续过程中修改了原数组中的某个数我们就必须去修改前缀和数组。
假设我们修改的是原数组中的第一个元素。由于原数组的前nnn项和必定包括第一个元素所以我们前缀和数组中的每一个元素都需要重新修改。那么这个过程的时间复杂度是O(n)O(n)O(n)的。此时这个前缀和数组相当于没有发挥作用。
总结一下当我们边修改数组中的某元素边求前缀和的时候我们原本的前缀和算法就会退化成O(n)O(n)O(n)。
二、树状数组
1、作用
当我们遇到原数组内的元素需要一边修改一边求区间和的时候就需要用到树状数组。
对于树状数组而言当修改一个原数组中的元素我们修改前缀和数组的时候此时的时间复杂度是O(logn)O(logn)O(logn)。当我们查询某段区间和的时候时间复杂度也是O(logn)O(logn)O(logn)。
与前缀和算法相比查询操作从O(1)O(1)O(1)到了O(logn)O(logn)O(logn)修改到操作从O(n)O(n)O(n)到了O(logn)O(logn)O(logn)。
2、算法分析
这个算法解释起来相当麻烦所以作者这里推荐一个讲解树状数组的视频
B站〔manim | 算法 | 数据结构〕 完全理解并深入应用树状数组 | 支持多种动态维护区间操作
3、算法实现
看过上面B站视频的讲解后我们发现树状数组重要的有三个函数一个函数是lowbits()一个函数是插入一个函数是查询。
1lowbits()
int lowbits(int x)
{return x -x;
}2插入
void add(int pos, int x)
{for(int i pos; i n; i lowbits(i))tree[i] x;return;
}3查询
int quary(int pos)
{int res 0;for(int i pos; i; i - lowbits(i))res tree[i];return res;
}
三、例题
P3374 【模板】树状数组 1
1、问题
题目描述
如题已知一个数列你需要进行下面两种操作 将某一个数加上 xxx 求出某区间每一个数的和
输入格式
第一行包含两个正整数 n,mn,mn,m分别表示该数列数字的个数和操作的总个数。
第二行包含 nnn 个用空格分隔的整数其中第 iii 个数字表示数列第 iii 项的初始值。
接下来 mmm 行每行包含 333 个整数表示一个操作具体如下 1 x k 含义将第 xxx 个数加上 kkk 2 x y 含义输出区间 [x,y][x,y][x,y] 内每个数的和
输出格式
输出包含若干行整数即为所有操作 222 的结果。
样例 #1
样例输入 #1
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4样例输出 #1
14
16提示
【数据范围】
对于 30%30\%30% 的数据1≤n≤81 \le n \le 81≤n≤81≤m≤101\le m \le 101≤m≤10 对于 70%70\%70% 的数据1≤n,m≤1041\le n,m \le 10^41≤n,m≤104 对于 100%100\%100% 的数据1≤n,m≤5×1051\le n,m \le 5\times 10^51≤n,m≤5×105。
数据保证对于任意时刻aaa 的任意子区间包括长度为 111 和 nnn 的子区间和均在 [−231,231)[-2^{31}, 2^{31})[−231,231) 范围内。
样例说明 故输出结果14、16
2、代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N 5e5 10;
int a[N];
ll tree[N];
int n, m;int lowbits(int x)
{return x -x;
}void add(int pos, int x)
{for(int i pos; i n; i lowbits(i))tree[i] x;return;
}ll quary(int pos)
{ll res 0;for(int i pos; i; i - lowbits(i))res tree[i];return res;
}void solve()
{cin n m;for(int i 1; i n; i )cin a[i];for(int i 1; i n; i )add(i, a[i]);while(m -- ){int op;cin op;if(op 1){int pos ,x;cin pos x;add(pos, x);}else{int l ,r;cin l r;cout quary(r) - quary(l - 1) endl;}}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();
}
