福
福

雨辰枫司的小栈

树状数组

  • 1018 字
  • 条评论
  1. 1. lowbit
  2. 2. 区域查询
  3. 3. 单点更新
  4. 4. code

用于快速查找和修改

lowbit

查找最低位1的位置

1
2
def lowbit(num:int) -> int:
    return num & (-num)

区域查询

查询 0 ~ idx 数据的和

1
2
3
4
5
6
def numSum(arr:list,idx:int):
    Sum = 0
    while idx > 0:
        Sum += arr[idx]
        idx -= lowbit(idx)
    return Sum

单点更新

更新 idx 的值为 val

1
2
3
4
5
def updata(arr:list,idx:int,val:int):
    lenT = len(arr)
    while idx < len:
        arr[idx] += val
        idx += lowbit(idx)

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class ArrayTree():
    def __init__(self,array = [],arrayLen = 0):
        self.array = array
        self.arrayLen = arrayLen

    def lowbit(self,num):
        return num & (-num)

    def updata(self,idx,val):
        if idx == 0:
            return
        while idx < self.arrayLen:
            self.array[idx] += val
            idx += self.lowbit(idx)

    def numSum(self,idx):
        Sum = 0
        while idx > 0:
            Sum += self.array[idx]
            idx -= self.lowbit(idx)
        return Sum

    def LRSum(self,left,right):
        return self.numSum(right) - self.numSum(left)