树状数组原理与实现
树状数组
树状数组（Binary Indexed Tree, or Fenwick Tree)是一种维护数组前缀和、区间和的数据结构思想和跳表有点类似:
- 跳表:添加索引，高效维护链表
- 树状数组:添加索引，高效维护数组
如何建立索引?
树状数组的一个结点索引的原始数据数量，与该结点编号在二进制下最低位的1有关。
- 1,3,5,7,…二进制下以1结尾，仅索引1个数据（自身)
- 2,6,10,14,…二进制下以10结尾，索引2个数据（自身、它前面的那个)
- 4,12,…二进制下以100结尾，索引4个数据（自身，前面的3个)
二进制分解与lowbit
任意正整数可以唯一分解为若干个不重复的2的次幂之和
lowbit(x)定义为×二进制下最低位的1和后面的O组成的数值（或者说×二进制分解下的最小次幂)
树状数组c的结点c[x]存储×前面lowbit(x)个数据（包括x)的和
- c[7]= a[7]
- c[12]= a[9] +a[10]+ a[11]+a[12]
树状数组的性质
每个内部结点c[]保存以它为根的子树中所有叶结点的和。
除树根外，每个内部结点c[x]的父亲是c[x + lowbit(x)]。
树的深度为O(log N)。
如果N不是2的整次幂，那么树状数组就是一个具有同样性质的森林结构。
查询
树状数组支持的第一个基本操作——查询前缀和
根据整数的二进制分解，可以把任意区间[1,x]拆成O(logN)个小区间
规律:
- 13前面的lowbit(13)=1个数，对应区间[13,13]，再往前一个数是12
- 12前面的lowbit(12)=4个数，对应区间[9,12]，再往前一个数是8
- 8前面的lowbit(8)=8个数，对应区间[1,8]，结束
查询
前缀和知道了，区间和（第l ~r个数据的和）可以直接由query® - query(l- 1)得到
时间复杂度:o(logN)——循环次数不超过二进制位数
规律:
- 13前面的lowbit(13)=1个数，对应区间[13,13]，再往前一个数是12
- 12前面的lowbit(12)=4个数，对应区间[9,12]，再往前一个数是8
- 8前面的lowbit(8)=8个数，对应区间[1,8]，结束
更新
树状数组支持的第二个基本操作是单点增加，即把某个数据×增加一个值delta
需要更新的索引就是c[x]以及它的所有祖先结点，至多O(logN)个
利用性质:每个内部结点c[x]的父亲是c[x + lowbit(x)]
时间复杂度:o(logN)
如果要修改一个数据，可以先算出差值，再执行add操作
实战
307.区域和检索–数组可修改
https://leetcode.cn/problems/range-sum-query-mutable/
class NumArray { private: vector<int> tree; vector<int> &nums; int lowBit(int x) { return x & -x; } void add(int index, int val) { while (index < tree.size()) { tree[index] += val; index += lowBit(index); } } int prefixSum(int index) { int sum = 0; while (index > 0) { sum += tree[index]; index -= lowBit(index); } return sum; } public: NumArray(vector<int>& nums) : tree(nums.size() + 1), nums(nums) { for (int i = 0; i < nums.size(); i++) { add(i + 1, nums[i]); } } void update(int index, int val) { add(index + 1, val - nums[index]); nums[index] = val; } int sumRange(int left, int right) { return prefixSum(right + 1) - prefixSum(left); } };
树状数组的局限性
树状数组有实现简单、效率高、省空间等诸多优势
但也有很大的局限性
维护的信息需要满足区间减法性质
- 不然无法通过前缀和相减得到区间和
- 例如无法直接拿来维护区间最值
不能很好地支持修改操作
- 单点修改需要先求出差值，转化为增加操作
- 基本上难以支持区间修改（修改连续的一段数据)
线段树的原理与实现
线段树
线段树(Segment Tree)是一种基于分治思想的二叉树结构，用于在区间上进行信息统计。
- 线段树的每个节点都代表一个闭区间。
- 线段树具有唯一的根节点，代表的区间是整个统计范围，如[1,N]。
- 线段树的每个叶节点都代表一个长度为1的元区间[x,x]。
- 对于每个内部节点[L,r]，它的左子节点是[L, mid]，右子节点是[mid + 1,r]，其中mid =(l+r)/2(向下取整)
除去树的最后一层，整棵线段树一定是一棵完全二叉树
树的深度为O(log N)
可以按照与二叉堆类似的“父子2倍”节点编号方法:
- 根节点编号为1。
- 编号为p的节点的左子节点编号为p * 2，右子节点编号为p* 2＋1。
这样一来，就能简单地使用数组来保存线段树
由于最后一层不一定是连续的，保存线段树的数组长度不要小于4N
区间最值问题（Range Maximum Query)
维护一个序列，支持:
- 查询区间最值（第l个数到第r个数的最大值)
- 单点修改（更新第×个数据)
- 区间统一修改（把第l个数到第r个数都置为val)
建树
Build(1,1, n)
时间复杂度O(n)——不超过结点数4n
单点修改
change(1,x, v)
- 从根（1号）结点出发，递归找到代表区间[x,x]的叶子结点
- 自底向上更新保存的信息
时间复杂度O(log(n))——每层一个结点，更新总次数不超过树高
区间查询
Query(1,l, r)，从根结点(1号结点）开始递归查询:
- 若L,r完全覆盖了当前结点代表的区间，则立即回溯，并且该结点的dat值为候选答案。
- 若左（右）子结点与[L,r]有重叠部分，则递归访问左(右)子结点。
时间复杂度O(log(n))——l, r各在树上划分出一条边界，最多形成2logn个候选区间
实战
307.区域和检索–数组可修改
https://leetcode.cn/problems/range-sum-query-mutable/
class NumArray { private: vector<int> segmentTree; int n; void build(int node, int s, int e, vector<int> &nums) { if (s == e) { segmentTree[node] = nums[s]; return; } int m = s + (e - s) / 2; build(node * 2 + 1, s, m, nums); build(node * 2 + 2, m + 1, e, nums); segmentTree[node] = segmentTree[node * 2 + 1] + segmentTree[node * 2 + 2]; } void change(int index, int val, int node, int s, int e) { if (s == e) { segmentTree[node] = val; return; } int m = s + (e - s) / 2; if (index <= m) { change(index, val, node * 2 + 1, s, m); } else { change(index, val, node * 2 + 2, m + 1, e); } segmentTree[node] = segmentTree[node * 2 + 1] + segmentTree[node * 2 + 2]; } int range(int left, int right, int node, int s, int e) { if (left == s && right == e) { return segmentTree[node]; } int m = s + (e - s) / 2; if (right <= m) { return range(left, right, node * 2 + 1, s, m); } else if (left > m) { return range(left, right, node * 2 + 2, m + 1, e); } else { return range(left, m, node * 2 + 1, s, m) + range(m + 1, right, node * 2 + 2, m + 1, e); } } public: NumArray(vector<int>& nums) : n(nums.size()), segmentTree(nums.size() * 4) { build(0, 0, n - 1, nums); } void update(int index, int val) { change(index, val, 0, 0, n - 1); } int sumRange(int left, int right) { return range(left, right, 0, 0, n - 1); } };
场景:线段覆盖
设计实现一个class，支持以下调用:
- cover(l, r, color)，把数轴上区间[L,r]染成color颜色
- query(x)，实时查询数轴上x坐标的颜色
10万次调用
坐标范围0~1e5
离散化
离散化就是把无穷集合中的若干个元素映射为有限集合以便于维护的方法
最常见的场景:坐标压缩
- 题目的坐标范围-1e9~1e9、任意实数等
- 其中只有N个坐标有用（在数据中出现了)
可以把出现过的坐标按大小顺序映射为1，2,3,… N
可用算法:
- 排序去重+二分
- 有序集合(sorted set)、有序映射(sorted map)
场景:线段覆盖（批处理＋无穷坐标)
cover(-1e9,700, red)
cover(-6.01,21.627, blue)
cover(98, 700, yellow)
query(12.345)
出现过的坐标（排序去重):{-1e9,-6.01,12.345,21.627,98,700}
映射为∶{1，2，3,4,5,6}
cover(1, 6, red)
cover(2,4, blue)
cover(5,6, yellow)
query(3)
实战
699.掉落的方块
https://leetcode.cn/problems/falling-squares/
class Solution { public: vector<int> fallingSquares(vector<vector<int>>& positions) { int n = positions.size(); vector<int> ret(n); map<int, int> heightMap; heightMap[0] = 0; // 初始时从 0 开始的所有点的堆叠高度都是 0 for (int i = 0; i < n; i++) { int size = positions[i][1]; int left = positions[i][0], right = positions[i][0] + positions[i][1] - 1; auto lp = heightMap.upper_bound(left), rp = heightMap.upper_bound(right); int rHeight = prev(rp)->second; // 记录 right + 1 对应的堆叠高度（如果 right + 1 不在 heightMap 中） // 更新第 i 个掉落的方块的堆叠高度 int height = 0; for (auto p = prev(lp); p != rp; p++) { height = max(height, p->second + size); } // 清除 heightMap 中位于 (left, right] 内的点 heightMap.erase(lp, rp); heightMap[left] = height; // 更新 left 的变化 if (rp == heightMap.end() || rp->first != right + 1) { // 如果 right + 1 不在 heightMap 中，更新 right + 1 的变化 heightMap[right + 1] = rHeight; } ret[i] = i > 0 ? max(ret[i - 1], height) : height; } return ret; } };
327.区间和的个数
https://leetcode.cn/problems/count-of-range-sum/
区间和=前缀和相减，即s[r]-s[l[lower, upper]，其中0<= l
枚举r，需要统计r前面有几个l满足s[r]- lower≤s[ss[r]- upper
从前往后扫描:
- “s[l]”是需要插入的东西
- 查询[s[r]- lower, s[r] - upper]中有几个
离散化＋线段树
struct SegNode { int lo, hi, add; SegNode* lchild, *rchild; SegNode(int left, int right): lo(left), hi(right), add(0), lchild(nullptr), rchild(nullptr) {} }; class Solution { public: SegNode* build(int left, int right) { SegNode* node = new SegNode(left, right); if (left == right) { return node; } int mid = (left + right) / 2; node->lchild = build(left, mid); node->rchild = build(mid + 1, right); return node; } void insert(SegNode* root, int val) { root->add++; if (root->lo == root->hi) { return; } int mid = (root->lo + root->hi) / 2; if (val <= mid) { insert(root->lchild, val); } else { insert(root->rchild, val); } } int count(SegNode* root, int left, int right) const { if (left > root->hi || right < root->lo) { return 0; } if (left <= root->lo && root->hi <= right) { return root->add; } return count(root->lchild, left, right) + count(root->rchild, left, right); } int countRangeSum(vector<int>& nums, int lower, int upper) { long long sum = 0; vector<long long> preSum = {0}; for (int v: nums) { sum += v; preSum.push_back(sum); } set<long long> allNumbers; for (long long x: preSum) { allNumbers.insert(x); allNumbers.insert(x - lower); allNumbers.insert(x - upper); } // 利用哈希表进行离散化 unordered_map<long long, int> values; int idx = 0; for (long long x: allNumbers) { values[x] = idx; idx++; } SegNode* root = build(0, values.size() - 1); int ret = 0; for (long long x: preSum) { int left = values[x - upper], right = values[x - lower]; ret += count(root, left, right); insert(root, values[x]); } return ret; } };
各种树形数据结构的对比
https://ke.qq.com/course/417774?flowToken=1041943
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
