阳江网红景点_华企网络_汕头seo服务_百度下载电脑版

树状数组：

又称二叉索引树，Binary Indexed Tree，BIT。
像树一样的数组（结构类型是完全二叉树，节点排列有规律，可使用数组模拟）。
用于单点修改，区间查询（计算前缀和、区间和）。查询和修改复杂度均为O(logn)。
核心思想：将原数组的索引（下标）在二进制表示下进行分组，每个分组维护一定范围内元素的累加和。
lowbit函数：非负整数在二进制表示下最右侧的1和其之后的所有0对应的数值。也可理解为该非负整数共有 $2^{k}$ 个子叶。
树状数组中的元素（节点）：二进制序列累和（即对应原数组中某个子序列的和），子序列的范围（二进制）：[x - lowbit(x) + 1, x]。
树状数组维护（单点修改）：修改树状数组中某下标对应元素及其所有父节点。依赖lowbit函数。
前缀和：通过树状数组获取从原数组开头到对应下标的总和，即区间[1,i]的总和。依赖lowbit函数。
区间查询：通过树状数组获取从原数组下标l 到下标r 的总和，即区间[l,r]的总和。依赖前缀和。
注意：① 树状数组的索引（下标）从1开始。② 本文a为原数组，t为树状数组，c为前缀和，s为区间和。
补充：二维树状数组，类似一维树状数组，注意行和列。
补充：树状数组和差分数组，可实现区间修改。本文忽略。

lowbit函数：

非负整数x，二进制表示下最低位（最右侧）的1和其之后的所有0对应的数值。即十进制为 $2^{k}$ （k为二进制最低位的1所在位置）。即有 $2^{k}$ 个子叶。

def lowbit(x:int):"""获取二进制中最右侧的1和其之后的所有0对应的数值"""return x & (-x)

补充：lowbit函数另一种实现方式为x&(x^(x-1))。

即x与(x-1)进行二进制异或运算，结果再与x进行二进制与运算。（异或运算：相同为1，不同为0。与运算：都为1结果为1，其余都为0）

def lowbit(x:int):"""获取二进制中最右侧的1和其之后的所有0对应的数值"""return x & (x ^ (x - 1))

树状数组的元素（节点）：

树状数组中每个元素为二进制序列累和（原数组中某个子序列的和），子序列的范围（二进制）：[x - lowbit(x) + 1, x]。

例如：下标12（二进制1100），lowbit函数结果为二进制100，二进制子序列范围[1001, 1100]，即t[12]=a[9]+a[10]+a[11]+a[12]。

单点修改：（树状数组维护）

修改树状数组中的某个元素，需修改元素本身及其所有父节点。依赖lowbit函数找到其父节点。

此处，单点修改由update函数实现。参数：i为下标（树状数组下标从1开始，最后一个元素下标为n即树状数组长度），val为值（例如：增加的值）。

def update(i:int, val:int):"""单点修改（树状数组维护）。i为下标，val为值，n为树状数组长度"""while i <= n:t[i] += val              # 修改值i += lowbit(i)           # 获取父节点

前缀和：（区间查询，区间[1,i]）

通过树状数组获取从原数组开头到对应下标的总和。

要获取前缀和，需将树状数组中相关的所有子序列的累和加总。依赖lowbit函数找到下一个子序列。

此处，前缀和由query函数实现。参数：i为下标（树状数组下标从1开始）。

def query(i:int):"""前缀和，i为下标，ans为合计"""ans = 0while i > 0:ans += t[i]             # 合计各子序列累和i -= lowbit(i)          # 获取下一个子序列return ans

区间查询：（区间[l,r]）

通过树状数组获取原数组中某个区间的总和，依赖前缀和query函数，即下标l到下标r的合计为s[l,r]=c[r]-c[l-1]。

说明：c[r]是区间[1,r]的总和，c[l-1]是区间[1,l-1]的总和，因此 c[r]-c[l-1]即为区间[l,r]的总和。

def range_query(l:int, r:int):"""区间查询（获取某区间的合计），l为起始(左侧)下标，r为结束(右侧)下标"""return query[r] - query[l - 1]

补充：二维树状数组：

0、lowbit函数：

def lowbit(x:int):"""获取二进制中最右侧的1和其之后的所有0对应的数值"""return x & (-x)

1、单点修改：（树状数组维护）

此处依赖 lowbit函数。

def update(i:int, j:int, val:int):"""二维树状数组，单点修改""""""i为行下标，j为列下标，val为值，n为树状数组的长度（n行），m为每行列数（m列）"""while i <= n:while j <= m:t[i][j] += valj += lowbit(j)i += lowbit(i)

2、前缀和：（子矩阵和查询，子矩阵[1, i][1, j]）

此处依赖 lowbit函数。

def query(i:int, j:int):"""二维树状数组，前缀和。i为树状数组的行下标，j为列下标"""ans = 0while i > 0:while j > 0:ans += t[i][j]j -= lowbit(j)i -= lowbit(i)

3、子矩阵和查询：（子矩阵和查询，子矩阵[i1, j1][i2, j2]）

此处依赖前缀和 query函数。

def range_query(i1:int, j1:int, i2:int, j2:int):"""二维树状数组，子矩阵和查询"""return query(i2, j2) - query(i2, j1 - 1) - query(i1 - 1, j2) + query(i1 -1, j1 - 1)

离散化：

将无限空间的有限个体映射到有限空间中，提高算法效率。
在数据相对大小不变的情况下，对数据进行相应缩小。
离散化，即f(元素值)=排序去重后的下标。
离散化有很多种方法。本文以STL算法离散化为例。
使用STL算法离散化主要步骤：① 排序。② 去重。③ 索引元素离散化后对应的值，即原各元素在排序去重后的数组中对应的下标。

方法一（二分查找）：

注：bisect库为数组二分算法库，使用二分算法往有序数组中插入元素而无需每次重排。

bisect.bisect_left(查找数组, 目标值)：查找插入点。即有序数组中第一个不小于目标值的元素下标，即若相同元素则最左侧的元素下标。
bisect.bisect_right(查找数组, 目标值)：查找插入点。即有序数组中第一个大于目标值的元素下标，即若相同元素则最右侧的元素下一个元素的下标。

imprt bisectdef discretization(nums:list)："""离散化。nums为数组"""# 排序，去重a = list(set(sorted(nums)))# 索引元素离散化后对应的值，即原各元素在排序去重后的下标, 下标从0开始n = len(nums)val_id = [0] * n            # 存放离散化后对应的值（即下标），初始化for i in range(n):# 二分查找第一个不小于目标值的元素下标val_id[i] = bisect.bisect_left(a, nums[i])return val_id# 简化
def discretization(nums:list)："""离散化。nums为数组"""# 排序，去重a = sorted(set(nums))# 索引元素离散化后对应的值，即原各元素在排序去重后的数组中的下标, 下标从0开始val_id = [bisect.bisect_left(a, nums[i]) for i in range(len(nums))]return val_id

方法二（键值对）：

def discretization(nums:list):"""离散化。nums为数组"""# 去重，排序a = sorted(set(nums))# 键值对 { 元素 : 去重排序后的数组中的下标 }, 下标从0开始val_id = {v : i for i, v in enumerate(a)}return val_id

离散化树状数组：

用于单点修改和前缀和的参数i（下标）为离散化后对应的值，即排序去重后的下标。

# 离散化，使用方法一（二分查找）
# 获取离散化后的下标，i为原数组中下标
index = val_id[i]
# 树状数组，前缀和
query(index)
# 树状数组，单点修改
update(index, val)# 离散化，使用方法二（键值对）
# 获取离散化后的下标,nums[i]为原数组中下标i对应的元素
index = val_id[nums[i]]
# 树状数组，前缀和
query(index)
# 树状数组，单点修改
update(index, val)

案例：【力扣】

（难度：困难）315. 计算右侧小于当前元素的个数

【Python3】

解题思路：将原数组离散化（从小到大排序并去重），离散化后各元素视为一个一个桶。

从后往前遍历原数组：

当前元素放入所有大于等于它的桶中（反过来说这些桶中存放的都是原数组中右侧小于等于它的元素），因此离散化后该桶之后都+1。
其前一个桶比当前元素小，前一个桶中存放的元素都是小于当前元素的。因此，前一个桶中的数量为右侧小于当前元素的个数。

使用树状数组动态维护前缀和，第i-1个桶的前缀和表示比i小的元素个数。

class Solution:def countSmaller(self, nums: List[int]) -> List[int]:n = len(nums)res = [0] * n             # 结果列表# 离散化，此处没有单独设置函数a = sorted(set(nums))val_id = {v : i + 1 for i, v in enumerate(a)}m = len(a)# 树状数组(下标从1开始，下标0此处存在但不使用),初始化t = [0] * (m + 1)# 从后往前遍历原数组for i in range(n - 1, -1, -1):# 获取离散化后的下标a_index = val_id[nums[i]]# 获取离散化后下标位置的前一个元素(查询前一个桶对应的前缀和)# 树状数组中的前缀和，此处没有单独设置函数j, ans = a_index - 1, 0while j > 0:ans += t[j]j -= j & -j                       # lowbit函数：i & -i，此处没有单独设置函数res[i] = ans# 离散化后下标位置及其后所有位置都+1# 树状数组中的单点修改，此处没有单独设置函数while a_index < m:t[a_index] += 1a_index += a_index & -a_index     # lowbit函数：i & -i，此处没有单独设置函数return res

面向对象：（设置类BIT，即树状数组）

class BIT:def __init__(self, n:int):"""树状数组初始化"""self.t = [0] * ndef lowbit(self, x:int):"""获取二进制表示时最低位的1及其后所有0对应的数值"""return x & (-x)def update(self, i:int, val:int = 1):"""单点修改"""while i < len(self.t):self.t[i] += val       # 元素中值默认+1i += self.lowbit(i)def query(self, i:int):"""前缀和（区间[1,i]）"""ans = 0while i > 0:ans += self.t[i]i -= self.lowbit(i)return ansclass Solution:def discretization(self, nums:list):"""离散化"""# 排序，去重a = sorted(set(nums))m = len(a)# 键值对{数值:去重排序后的下标}，树状数组的下标从1开始val_id = {v : i + 1 for i, v in enumerate(a)}# 返回离散化后的键值对和离散化后的长度return val_id, mdef countSmaller(self, nums: List[int]) -> List[int]: n = len(nums)res = [0] * n                             # 结果列表val_id, m = self.discretization(nums)     # 离散化bitree = BIT(m + 1)                       # 树状数组# 从后往前遍历原数组for i in range(n - 1, -1, -1):# 获取排序去重后对应的下标a_index = val_id[nums[i]]# 离散化后，该元素的前一个元素的前缀和为原数组中右侧小于该元素的个数res[i] = bitree.query(a_index - 1)# 离散化后，该元素后所有元素都+1，因为其后所有元素都大于等于该元素bitree.update(a_index)               return res

此题还有其他方法：分治算法。