Binary Indexed Tree

Concepts

讲解：https://www.youtube.com/watch?v=CWDQJGaN1gY

适用场景：update较为频繁。

普通的pre sum computation，如果后续有值发生了更改，需要再重新计算一次这个pre sum 数组，时间复杂度为O(n)。但BIT，只需要对个别数值进行更改，时间复杂度为O(log n)。

但缺点是，普通的pre sum计算sum时，时间复杂度为O(1)。BIT需要O(log n)。

For example, original array = [0, 1, 2, 3, 4]

How to create BIT?

Create a new array with length 6 (5 + 1). [0, 0, 0, 0, 0, 0] Read each number from the original array and update related values in BIT following the RULE. RULE: 1. added the number to the value at (index + 1). 2. Update the next value in BIT until index is out of bound. How to get the sum from BIT?

If we want to sum(0, i), we start from index i + 1 in BIT. ans = 0. ans += BIT[i + 1] Get the parent of i + 1, ans += BIT[p[i + 1]], until the index <= 0

How to get Next?
1. 2's complement
2. &
3. add

For example, index = 5
1. Check the number with index 6 in BIT. BIT[6] += num[5]
2. 6 = 0110, 2's complement of 6 = 1001 + 1 = 1010
3. 0110 & 1010 = 0010
4. 0110 + 0010 = 1000. So next would be index 8 in BIT

________________________________________________________________________

How to get Parent?
1. 2's complement
2. &
3. subtract

For example, we want to get the sum(0, 3)
1. ans = 0
2. ans += BIT[4]
3. 4 = 0100, 2s complement of 4 = 1011 + 1 = 1100
4. 0100 & 1100 = 0100
5. 0100 - 0100 = 0. So parent of 4 would be 0.


0
1    2    4    8
     3    5 6  9 10 12
            7    11 13 14
                       15

经典题目

308 Range Sum Query 2D - Mutable

Regular pre sum

def __init__(self, matrix):
    """
    :type matrix: List[List[int]]
    """
    self.matrix = matrix
    self.leftToRight = []
    
    for l in matrix:
        temp = []
        for j in range(len(l)):
            if j == 0:
                temp.append(l[j])
            else:
                temp.append(temp[j - 1] + l[j])
        self.leftToRight.append(temp)

# Time: O(m)
def update(self, row, col, val):
    """
    :type row: int
    :type col: int
    :type val: int
    :rtype: void
    """
    for j in range(col, len(self.matrix[0])):
        self.leftToRight[row][j] += val - self.matrix[row][col]
    
    self.matrix[row][col] = val

# Time: O(n)
def sumRegion(self, row1, col1, row2, col2):
    """
    :type row1: int
    :type col1: int
    :type row2: int
    :type col2: int
    :rtype: int
    """
    ans = 0
    for i in range(row1, row2 + 1):
        ans += self.leftToRight[i][col2] - self.leftToRight[i][col1] + self.matrix[i][col1]
    
    return ans

Binary Indexed Tree

def __init__(self, matrix):
    """
    :type matrix: List[List[int]]
    """
    if matrix is None or len(matrix) == 0 or len(matrix[0]) == 0:
        return
    
    self.nums = [[0 for j in xrange(len(matrix[0]))] for i in xrange(len(matrix))]
    self.tree = [[0 for j in xrange(len(matrix[0]) + 1)] for i in xrange(len(matrix) + 1)]
    
    for i in xrange(len(matrix)) :
        for j in xrange(len(matrix[0])) :
            self.update(i, j, matrix[i][j])
    
    print self.tree
    
# Time: O(m)
def update(self, row, col, val):
    """
    :type row: int
    :type col: int
    :type val: int
    :rtype: void
    """
    delta = val - self.nums[row][col]
    self.nums[row][col] = val
    i = row + 1
    while i < len(self.tree):
        j = col + 1
        while j < len(self.tree[0]):
            self.tree[i][j] += delta
            j += j & (-j)
        i += i & (-i)
    
    
# Time: O(n)
def sumRegion(self, row1, col1, row2, col2):
    """
    :type row1: int
    :type col1: int
    :type row2: int
    :type col2: int
    :rtype: int
    """
    return self.sumHelper(row2, col2) + self.sumHelper(row1 - 1, col1 - 1) \
            - self.sumHelper(row1 - 1, col2) - self.sumHelper(row2, col1 - 1)
    
def sumHelper(self, row, col):
    ans = 0
    i = row + 1
    while i > 0:
        j = col + 1
        while j > 0:
            ans += self.tree[i][j]
            j -= j & (-j)
        i -= i & (-i)
    return ans