高级数据结构-树状数组(Fenwick Tree)

类模版

def lowerBits(x):
    return x & (-x)


class BinaryIndexTree:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    def update(self, index, delta):
        while index <= self.size:
            self.tree[index] += delta
            index += lowerBits(index)

    def query(self, index):
        res = 0
        while index >= 1:
            res += self.tree[index]
            index -= lowerBits(index)
        return res

    def rangeQuery(self, left, right):
        return self.query(right) - self.query(left - 1)

树状数组的结构与使用非常简洁有效。

动机

给出一个数组$a[n]$，问题给出的需求为查询下标为$[\text{left},\text{right}]$全闭区间内的数组和。记区间长度为$m$，则每次查询的时间复杂度为$O(m)$，当查询次数$k$为$O(n)$级别且区间长度也为$O(n)$级别时。总体时间复杂度为$O(n^2)$。

第一种改进思路
使用前缀和数组$b[n]$，在查询时使用差分计算。这样单次查询的时间复杂度为$O(1)$。
然而我们的问题此时如果提出额外的需求，不光查询，还包含若干施加到数组$a[n]$某元素的修改操作。
记每次修改前元素$a[i]$为$c_i$，修改后为$c_i^{\prime }$。前缀和数组需要对$b[j],j\ge i$，进行差分更新，每个元素的delta为$c_i^{\prime }-c_i$。即修改操作的时间复杂度为$O(n-i)$，若$i$服从均匀分布，修改操作的时间复杂度为$\Theta (\frac{n}{2})$。

树状数组
以上分析指出，在数组既要查询又要修改时需要一种更优秀的数据结构。前缀和数组在一定程度上缓解了问题。只要能改善修改时的时间复杂度即可。修改时时间复杂度高的原因是前缀和数组$b[i]$管辖的是$[0,i]$的区间和，如果可以有效缩短管辖区间则可以在数组修改时做更少的数据结构存储修改。

树状数组的数据存储结构tree为1-index。每个元素$\text{tree}[i]$，管辖的$a[i]$
个数为$\text{lowBit}(i)$，具体区间为$[i-\text{lowBit}(i)+1,i]$。

Low-Bits
一个非负整数的二进制数制表示中从低位开始数第一个1以及所有低位的0共同构成一个数的低位比特。

此时单次查询或更新操作的时间复杂度均为$O(\log (n))$（仅证明单点查询）
证明:

• 查询：
  给出一个索引$i$，想获得$[0,i]$区间数组$a[j]$的元素和。$\text{tree}[i]$保存了$[i-\text{lowBit}(i)+1,i]$的区间和，将此区间结果加到res上，迭代$i^{\prime }=i-\text{lowBit}(i)$。

1. 首先证明迭代一定停止：
   $i-\text{lowBit}(i)+1\le i$，i为奇数时取等号。$i^{\prime }=i-\text{lowBit}(i)<i-\text{lowBit}(i)+1\le i$，所以迭代严格单调减，又因为$i\ge 1$，所以有下界。证毕。
2. 证明操作至多$\lceil \log (n+1)\rceil$次：
   因为每次迭代$i$减少一个二进制1，而$i$的二进制1至多$\lceil \log (i+1)\rceil$位，$\lceil \log (i+1)\rceil \le \lceil \log (n+1)\rceil$。证毕。

• 更新：
  我们需要更新所有包含了$a[i]$的$\text{tree}[j]$，首先$\text{tree}[i]$一定包含，因为区间是全闭的。数据是类似前缀和的，因此$j\ge i$，需要证明递推公式$j^{\prime }=j+\text{lowBit}(j)$的正确性与次数渐进上限为$O(\log (n))$。

1. 观察到$[k-\text{lowBit}(k)+1,k]$是$[k^{\prime }-\text{lowBit}(k^{\prime })+1,k^{\prime }]$的子集，其中$k^{\prime }$使用以上公式迭代产生。因为新区间
   $$[k+\text{lowBit}(k)-\text{lowBit}(k+\text{lowBit}(k))+1,k+\text{lowBit}(k)]$$
   $k<k+\text{lowBit}(k)$，且
   $$\begin{array}{rl}& (k+\text{lowBit}(k)-\text{lowBit}(k+\text{lowBit}(k))+1)-(k-\text{lowBit}(k)+1)\\ & =2\text{lowBit}(k)-\text{lowBit}(k+\text{lowBit}(k))\end{array}$$
   $k+\text{lowBit}(k)$会使$k$的$\text{lowBit}(k)$至少左移一位，即至少为$2\text{lowBit}(k)$，遇到进位情况则会更大。因此$(2)$式小于等于$0$。
   因此以上迭代公式涉及的$k$确实都需要更新。
   接着需要证明没有任何包含$a[i]$的$\text{tree}[j]$被落下。上述证明表明使用递推公式可以找出一个数列$\text{tree}[j_k]$，这个数列的所有项是需要更新的项，假设存在其它包含$a[i]$的$\text{tree}[j]$被落下，按照递推序，我们可以定义这些被落下的项组成数列的首项，若包含多组数列，将首项中下标最小的取出，证明这项也已经被包含即可。记这项为$\text{tree}[i+d],d>0$。
   明显$\text{tree}[i]$是按照下标排序第一个包含$a[i]$的项，且已经包含在递推公式中。则有$i+d-\text{lowBit}(i+d)+1<i<i+d$，第一个不等式可以推出$d+1<\text{lowBit}(i+d)$。
   当$\text{lowBit}(i)\ne \text{lowBit}(d)$时， lowBit ( i + d ) = min ⁡ { lowBit ( i ) , lowBit ( d ) } \text{lowBit}(i+d) = \min \{ \text{lowBit}(i), \text{lowBit}(d) \} lowBit(i+d)=min{lowBit(i),lowBit(d)}，第一种情况$d+1<\text{lowBit}(d)\le d$且$\text{lowBit}(d)<\text{lowBit}(i)$矛盾，第二种情况$d+1<\text{lowBit}(i)$且$\text{lowBit}(i)<\text{lowBit}(d)$，即$d+1<\text{lowBit}(d)\le d$矛盾。
   因此$\text{lowBit}(i)=\text{lowBit}(d)$，由于一定有$\text{lowBit}(d)\le d$，推出$\text{lowBit}(i)\le d$。所以满足条件的最小$d$为$\text{lowBit}(i)$，即$\text{tree}[i+d]$是递推公式中包含的项，与假设矛盾。

Tips: 数学归纳法正向推导也是可行的。

2. $j^{\prime }=j+\text{lowBit}(j),j\le n$迭代至多$O(\log (n))$次。因为每次会使$j$的$\text{lowBit}(j)$至少左移一位，总共只有$O(\log (n))$位。
   审讯树也是可以用来证明与理解树状数组的方式。

离散化树状数组

在例如扫描线等问题中，数据定义在无限二维平面上，某维度的值可能取值范围很大，但是数据相对来说较为稀疏。可以将所有值按照序进行排序压缩映射到一个更小的范围来节约树状数组的空间。一般实际应用都是使用状态压缩了的离散化树状数组。

解题应用

一维离散化问题

LCR 170. 交易逆序对的总数
常规解法：

class Solution:
    def reversePairs(self, record: List[int]) -> int:        
        n=len(record)
        if n==0:
            return 0
        record_=record.copy()
        record_.sort()
        record_compression = {record_[0]:1}
        r_idx=2
        for r in record_[1:]:
            if record_compression.get(r, None):
                pass 
            else:
                record_compression[r]=r_idx 
                r_idx+=1 
        bit = BinaryIndexTree(len(record_compression))
        res=0
        # for i in range(n-1, -1, -1):
        #     r=record[i]
        #     res+=(n-1-i-bit.rangeQuery(record_compression[r], len(record_compression)))
        #     bit.update(record_compression[r])
        bit.update(record_compression[record[0]])
        for i in range(1, n):
            r=record[i]
            res+=(i-bit.query(record_compression[r]))
            bit.update(record_compression[r])
        return res

更巧妙解法：
从后向前遍历，出现了更小的就是逆序。可以节省一部分减法。

class Solution:
    def reversePairs(self, record: List[int]) -> int:        
        n=len(record)
        if n==0:
            return 0
        record_=record.copy()
        record_.sort()
        record_compression = {record_[0]:1}
        r_idx=2
        for r in record_[1:]:
            if record_compression.get(r, None):
                pass 
            else:
                record_compression[r]=r_idx 
                r_idx+=1 
        bit = BinaryIndexTree(len(record_compression))
        res=0

        for i in range(n-1, -1, -1):
            r=record[i]
            res+=bit.query(record_compression[r]-1)
            bit.update(record_compression[r])
        return res

扫描线配合树状数组解决计算几何问题（二维）

3382. 用点构造面积最大的矩形 II

class Solution:
    def maxRectangleArea(self, x_coords: List[int], y_coords: List[int]) -> int:
        def get_lowest_bit(x):
            return x & -x

        class FenwickTree:
            def __init__(self, size):
                self.tree = [0] * (size + 1)
                self.size = size

            def update(self, index, delta=1):
                while index <= self.size:
                    self.tree[index] += delta
                    index += get_lowest_bit(index)

            def query(self, index):
                result = 0
                while index >= 1:
                    result += self.tree[index]
                    index -= get_lowest_bit(index)
                return result

        # Compress y-coordinates to a unique index
        y_compression = {}
        max_area = -1
        events = [list(event) for event in zip(x_coords, y_coords)]
        events.sort(key=lambda x: (x[0], x[1]))
        y_values = [events[0][1]]
        vertical_lines = [[events[0]]]

        for event in events[1:]:
            y_values.append(event[1])
            if event[0] != vertical_lines[-1][0][0]:
                vertical_lines.append([event])
            else:
                vertical_lines[-1].append(event)
        y_values.sort()

        # Assign compressed indices to y-values
        y_index = 1
        for i, y in enumerate(y_values):
            if y not in y_compression:
                y_compression[y] = y_index
                y_index += 1

        bit_tree = FenwickTree(len(y_compression))
        y_pair_count_map = {}

        bit_tree.update(y_compression[vertical_lines[0][0][1]])
        for i, point in enumerate(vertical_lines[0][1:], start=1):
            ya = vertical_lines[0][i - 1][1]
            yb = point[1]
            bit_tree.update(y_compression[yb])
            cnt = bit_tree.query(y_compression[yb]) - bit_tree.query(y_compression[ya] - 1)
            y_pair_count_map[(ya, yb)] = [cnt, vertical_lines[0][i - 1][0]]

        for j, vertical in enumerate(vertical_lines[1:], start=1):
            bit_tree.update(y_compression[vertical[0][1]])
            for i, point in enumerate(vertical[1:], start=1):
                ya = vertical[i - 1][1]
                yb = point[1]
                bit_tree.update(y_compression[yb])
                cnt = bit_tree.query(y_compression[yb]) - bit_tree.query(y_compression[ya] - 1)
                if (ya, yb) in y_pair_count_map:
                    if cnt - y_pair_count_map[(ya, yb)][0] == 2:
                        current_area = (yb - ya) * (point[0] - y_pair_count_map[(ya, yb)][1])
                        max_area = max(max_area, current_area)
                y_pair_count_map[(ya, yb)] = [cnt, point[0]]
        return max_area