树状数组b站博主
灵神博主

tree数组：Tree[i] 存储的是原本的数组中num[i - (i&-i)+1]到nums[i]的和
更新的时候，num[i[更新，逐一修改num[i+(i & -i)]

307.区间和检索-数组可修改

题目实战

总的代码：

class NumArray:__slots__ = 'nums', 'tree'def __init__(self, nums: List[int]):n = len(nums)# 注意，nums 是从0-n-1的下标，tree是1-n的下标self.nums = [0] * n  # 使 update 中算出的 delta = nums[i]self.tree = [0] * (n + 1)for i, x in enumerate(nums):self.update(i, x)def update(self, index: int, val: int) -> None:delta = val - self.nums[index]self.nums[index] = vali = index + 1# 注意这个+1的操作是下标的对应的操作while i < len(self.tree):self.tree[i] += deltai += i & -idef prefixSum(self, i: int) -> int:s = 0while i:s += self.tree[i]i &= i - 1  # i -= i & -i 的另一种写法return sdef sumRange(self, left: int, right: int) -> int:return self.prefixSum(right + 1) - self.prefixSum(left)

1395.统计作战单位数

力扣参照博主

思路分析：这个题目的关键就是在于，外层的循环想需要遍历全部的rating，然后就是统计rating[i]的前面有多少个元素小于 和 大于 rating[i[,以及对应的rating[i[后面有多少个元素小于和大于rating[i]
一般情况下，我们就是通过暴力进行统计的，对于这个题目来说暴力的时间的复杂度就是 O(n^2)，对于这个题目来说，由于rating.length<=1000,所以并不会超时，但是优化来说，还是使用树状数组来维护最好，树状数组由于在更新和查询都是 o(logn),所以总体的时间复杂度是 o(nlogn)

# 暴力情况
class Solution:def numTeams(self, rating: List[int]) -> int:ans = 0n = len(rating)for i in range(1, n-1):# 前序元素small1 = 0      # 前序元素中小于当前值的元素数目for j in range(i):if rating[j] < rating[i]:small1 += 1# large1：前序元素中大于当前值的元素数目【满足small1+large1=i】large1 = i - small1# 后序元素small2 = 0      # 后序元素中小于当前值的元素数目for j in range(i+1, n):if rating[j] < rating[i]:small2 += 1# large2：后序元素中大于当前值的元素数目【满足small2+large2=n-1-i】large2 = n-1 - i - small2ans += small1*large2 + large1*small2return ans

如何理解这个树状数组的作用？
我们开始的时候并不是为了树状数组而使用树状数组，对于这个题目来说，我们可以按照rating[i]的顺序，使用一个数组nums[i]=1,然后对于当前的rating[i],我们只用求解 nums[i] 前面的前缀和就知道有多少个元素小于nums[i]

# 树状数组
class Solution:def numTeams(self, rating: List[int]) -> int:def lowbit(x):          # lowbit函数：二进制最低位1所表示的数字return x & (-x)def add(i, delta):      # 单点更新：执行+deltawhile i<len(tree):tree[i] += deltai += lowbit(i)def query(i):           # 前缀和查询presum = 0while i>0:presum += tree[i]i -= lowbit(i)return presum'''主程序'''# 离散化：绝对数值转秩次rankuniques = sorted(rating)    # rating没有重复值rank_map = {v:i+1 for i,v in enumerate(uniques)}    #【rank从1开始】# 构建树状数组tree = [0] * (len(rank_map) + 1)    # 树状数组下标从1开始# 枚举中间点ans = 0n = len(rating)add(rank_map[rating[0]], 1)     # 先将第一个元素入列for i in range(1, n-1):         # 从第二个元素开始遍历，直至倒数第二个元素rank = rank_map[rating[i]]  # 当前元素的排名/秩次small1 = query(rank-1)      # 查询前序元素中排名<rank的元素数目large1 = i - small1         # small1 + large1 = ismall2 = (rank-1) - small1  # 共有rank-1个元素排名<rank：small1 + small2 = rank-1large2 = n-1 - i - small2   # small2 + large2 = n-1-iadd(rank, 1)                # 当前元素入列ans += small1*large2 + large1*small2return ans