算法：树状数组

树状数组可以理解一种数的存储格式。

面试题 10.10. 数字流的秩

假设你正在读取一串整数。每隔一段时间，你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。
请实现数据结构和算法来支持这些操作，也就是说：
实现 track(int x) 方法，每读入一个数字都会调用该方法；
实现 getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数。

面试题 10.10. 数字流的秩

class StreamRank {vector<int> v;int lowbit(int x) {return x & -x;}
public:StreamRank(): v(50002, 0) {}void track(int x) {++x; //x + 1是因为树状数组处理的元素下标从1开始while (x <= 50001) {v[x]++;x += lowbit(x);}}int getRankOfNumber(int x) {++x;int ans = 0;while (x) {ans += v[x];x -= lowbit(x);}return ans;}
};

class StreamRank:def __init__(self):self.l = [0]*50002def lowBit(self, x):return x & (-x)def track(self, x: int) -> None:x += 1while x <= 50001:self.l[x] += 1x += self.lowBit(x)def getRankOfNumber(self, x: int) -> int:x += 1ans = 0while x:ans += self.l[x]x -= self.lowBit(x)return ans

327. 区间和的个数

给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

327. 区间和的个数
区间过大，hash，然后到树状数组。

class Solution:def countRangeSum(self, nums, lower: int, upper: int) -> int:n = len(nums)prefixs = [0]*nt = 0ans = 0for i in range(n):t += nums[i]prefixs[i] = tif lower<= t<= upper:ans += 1s = set()for i in range(n):s.add(prefixs[i])s.add(prefixs[i]-lower)s.add(prefixs[i] - upper)l = sorted(s)d = {x: i+1 for i, x in enumerate(l)}  # hash到固定长度trie = [0]*(len(d)+1)  # 树状数组for i in range(n):left, right = d[prefixs[i]-upper], d[prefixs[i]-lower]ans += self.query(trie, right) - self.query(trie, left-1)self.insert(trie, d[prefixs[i]])return ansdef query(self, trie, x):ans = 0while x:ans += trie[x]x -= x & (-x)return ansdef insert(self, trie, x):while x < len(trie):trie[x] += 1x += x & (-x)

315. 计算右侧小于当前元素的个数

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

315. 计算右侧小于当前元素的个数

class Solution:def countSmaller(self, nums: List[int]) -> List[int]:n = len(nums)l = [0]*20002 # -10000~10000 -> 2~20002 因为求小于x的值，x=2，count输入x=1ans = [0]*nfor i in range(n-1,-1,-1):x = nums[i] + 10002ans[i] = self.count(l, x-1)self.insert(l, x)return ansdef count(self, l, x):ans = 0while x:ans += l[x]x -= self.lowBit(x)return ansdef lowBit(self, x):return x & (-x)def insert(self, l, x):while x < len(l):l[x] += 1x += self.lowBit(x)

算法学习笔记(2) : 树状数组