做公司网站要什么资料,网站开发多少钱一天是,网站模块是指什么地方,申诉网站风险文章目录 前言问题引入问题分析树状数组lowbit树状数组特性初始化一个树状数组更新操作前缀和计算区间查询 总结 前言
原题的连接 最近刷leetcode的每日一题的时候#xff0c;遇到了一个区间查询的问题#xff0c;使用了一种特殊的数据结构树状数组#xff0c;学习完之后我… 文章目录 前言问题引入问题分析树状数组lowbit树状数组特性初始化一个树状数组更新操作前缀和计算区间查询 总结 前言
原题的连接 最近刷leetcode的每日一题的时候遇到了一个区间查询的问题使用了一种特殊的数据结构树状数组学习完之后我不禁感叹这个数据结构设计的巧妙下面是我的学习笔记。
问题引入
给你一个数组 nums 请你完成两类查询。
其中一类查询要求 更新 数组 nums 下标对应的值 另一类查询要求返回数组 nums 中索引 left 和索引 right 之间 包含 的nums元素的 和 其中 left right 实现 NumArray 类
NumArray(int[] nums) 用整数数组 nums 初始化对象void update(int index, int val) 将 nums[index] 的值 更新 为 valint sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间 包含 的nums元素的 和 即nums[left] nums[left 1], …, nums[right]
问题分析
这个问题我们可以总结为
单点修改就是一次只修改一个数与之相对的是区间修改区间查询查询某一个区间的和
我们如果用暴力的求解在每次单点修改之后都需要重新计算一下区间的和显然效率低下。 那我们如果使用前缀和数组进行求解这样所有的区间和问题都可以转换成区间边界前缀和相减但是每次单点修改之后修改位之后的所有前缀和都需要修改。 通过上面的思考我们发现每次单点修改之后重新计算前缀和的成本太高了。那有没有一种方法能缩小这种由于单点更新导致的前缀和重新计算
树状数组
我们先看一下树状数组长什么样子 假设我们现在有一个数组a[]{1,5,7,4,3,2,1,6,7,3,0,4,9}
然后上图展示的就是一个树状数组树状数组实际上一个数组但是在逻辑结构上看做一个树形结构。其实和堆的底层结构是一样的。 数组的每个元素实际上代表的是某一个区间和而树状数组设计巧妙的就是这个区间覆盖的长度的设计 然后我们来逐一分析如何得到这么一颗树形结构
lowbit
什么一个数的lowbit lowbit是最截取一个数二进制最低位的二进制1 到最末尾 例如数字6他的二进制位为0110取出它的lowbit位就变成了10转换成十进制就是2 例如数字8他的二进制为1000取出它的lowbit位就变成了1000转换成十进制就是8 那么如何计算数字a的lowbit呢 这个只需要 a(-a)就是a与上a的补码加1补码加一使得最右边的1右边的所有位与a的二进制位均相同而左边的位全部与a的二进制相反这样一个操作直接能取出。
所以lowbit的函数就为 // 计算lowbit数值 int lowbit(int x) {return x (-x);}树状数组特性
理解了lowbit的概念之后我们在看这个树状数组 我们对树状数组t[i]的定义是原数组a在区间[i-lowbit(i),i]区间上的和i的下标从1开始
我们发现了树状数组实际上遵循以下规律
t[i] 实际上代表的是一个a数组的某个区间的和而这个区间长度正好是lowbit(i)t[i]的父节点为t[ilowbit(i)]而父区间一定是包含子区间的所以子区间发生更新之后一定需要修改父区间t[i]实际上就是数组在[i-lowbit(i)1,i]这个区间上面的和
初始化一个树状数组
如果要初始化一个树状数组我们需要定义两个数组一个是用来保存原始的数组一个用来保存树状数组 初始化树状数组其实很简单我们只需要牢记规律1计算t[i]时而为右边界通过规律1反推出左边界就能计算出区间和
class TreeArray {private:vectorint t; // 树状数组vectorint v; // 原始数组// 计算lowbit数值 int lowbit(int x) {return x (-x);}
public:// 初始化树状数组void Init(const vectorint x) {// 注意这里的v和t 下标都不是从0开始的而是从1开始的v.resize(x.size() 1);copy(x.begin(), x.end(), (v.begin()));t.resize(x.size() 1, 0);for (int i 1; i x.size(); i) {for (int j i - lowbit(i) 1; j i; j) {t[i] v[j];}}}
};
更新操作
更新操作也十分简单由于更新之后需要修改某些区间和这里牢记规律2从子区间向上更新父区间然后更新v和t数组
例如下面我们需要修改下标为3的值将它的值修改为4那么区间和就需要增加1然后将所有包含下标为3的区间都进行修改 class TreeArray {private:vectorint t; // 树状数组vectorint v; // 原始数组// 计算lowbit数值 int lowbit(int x) {return x (-x);}
public:// 初始化树状数组void Init(const vectorint x) {v.resize(x.size() 1);copy(x.begin(), x.end(), (v.begin()));t.resize(x.size() 1, 0);for (int i 1; i x.size(); i) {for (int j i - lowbit(i) 1; j i; j) {t[i] v[j];}}}void Update(int index, int val) {// 传入的index是从0开始的但是我们这里的树状数组下标是从1开始int dif val - v[index 1]; // 这里我们计算一个差值v[index 1] val;// 修改index的所有的父节点for (int i index 1; i t.size(); i lowbit(i)) {t[i] dif;}}
};前缀和计算
前缀和这个就更简单了更具树状数组的定义 我们对树状数组t[i]的定义是原数组a在区间[i-lowbit(i)1,i]区间上的和i的下标从1开始 比方说我们要计算下标为7的前缀和我们可以拆成t[7]t[6]t[4]而我们发现7减去区间长度lowbit(7)就是t[6]而t[6]减去区间长度t[4]… 这就是线段树的设计巧妙之处把前缀和转换成多个树状数组元素相加 class TreeArray {
private:vectorint t; // 树状数组vectorint v; // 原始数组// 计算lowbit数值 int lowbit(int x) {return x (-x);}
public:// 初始化树状数组void Init(const vectorint x) {v.resize(x.size() 1);copy(x.begin(), x.end(), (v.begin()));t.resize(x.size() 1, 0);for (int i 1; i x.size(); i) {for (int j i - lowbit(i) 1; j i; j) {t[i] v[j];}}}void Update(int index, int val) {// 传入的index是从0开始的但是我们这里的树状数组下标是从1开始int dif val - v[index 1];v[index 1] val;// 修改index的所有的父节点for (int i index 1; i t.size(); i lowbit(i)) {t[i] dif;}}// 算出index的前缀和int GetPrefixSum(int index) {int sum 0;for (int i index 1; i 0; i - lowbit(i)) {sum t[i];}return sum;}
};区间查询
我们直接把区间查询转换成 前缀和相减
class TreeArray {private:vectorint t; // 树状数组vectorint v; // 原始数组// 计算lowbit数值 int lowbit(int x) {return x (-x);}
public:// 初始化树状数组void Init(const vectorint x) {v.resize(x.size() 1);copy(x.begin(), x.end(), (v.begin()));t.resize(x.size() 1, 0);for (int i 1; i x.size(); i) {for (int j i - lowbit(i) 1; j i; j) {t[i] v[j];}}}void Update(int index, int val) {// 传入的index是从0开始的但是我们这里的树状数组下标是从1开始int dif val - v[index 1];v[index 1] val;// 修改index的所有的父节点for (int i index 1; i t.size(); i lowbit(i)) {t[i] dif;}}// 算出index的前缀和int GetPrefixSum(int index) {int sum 0;for (int i index 1; i 0; i - lowbit(i)) {sum t[i];}return sum;}// 区间查询int Select(int begin, int end) {return GetPrefixSum(end) - GetPrefixSum(begin - 1);}
};总结
树状数组 实际上是对前缀和的优化前缀和计算的是[0,i]的和如果一个修改就要对所有的区间和修改但是树状数组将区间的长度通过lowbit的巧妙构造使得每次单点修改所要更新的区间和始终不超过O(logN)。
树状数组的使用条件遇到这种情况直接默写模版
单点更新区间查询
然后默写树状数组的时候牢记三个规律AC这类题应该没有多大问题
