python implements fenwick tree algorithm case

Introduction to the fenwick tree algorithm

Fenwick Tree, also known as Binary Indexed Tree or tree-like array, is a data structure first introduced by Peter M. Fenwick in 1994 under the title "A New Data Structure for Cumulative Frequency Tables".

Fenwick Tree is mainly used to efficiently calculate the prefix sum of numeric sequences (arrays), and also supports element update operations with log time complexity.

Basic concepts

Fenwick Tree maintains an array to record the sum of the original array in different intervals, so as to answer prefixes and queries and single point updates within the time complexity of O(log n).
Compared to traditional prefixes and arrays, Fenwick Tree is more efficient when handling frequent element updates because it does not require rebuilding the entire prefixes and arrays.

principle

Fenwick Tree uses the binary representation of integers to associate each element with multiple intervals and store the sum of these intervals in an array of Fenwick Tree.
The corresponding node of each index i in the Fenwick Tree stores the sum of all elements in the interval from i - lowbit(i) + 1 to i (included), where lowbit(i) is the value corresponding to 1 of the lowest bit in i under the binary representation.

Main operations

Single point update: When an element in the original array needs to be updated, the Fenwick Tree reflects this change by modifying the values of the corresponding nodes and all of its ancestor nodes in the Fenwick Tree. The time complexity of this process is O(log n).
Prefix and query: For a given index x, Fenwick Tree calculates the sum of elements from the beginning of the array to the index x (included) by accumulating the values of all nodes on the path from x to the root node. The time complexity of this process is also O(log n).

accomplish

The implementation of Fenwick Tree usually includes the following parts:

Initialization: Create a Fenwick Tree array of the same length as the original array and initialize all elements to 0.
Single point update: Update the value of the corresponding node in the Fenwick Tree by continuously accumulating index + lowbit(index).
Prefix and query: By continuously subtracting index - lowbit(index), accumulate the corresponding node values in the Fenwick Tree until the index is 0.

Example

Assume that there is an array a = [1, 2, 3, 4, 5], we can build a Fenwick Tree to efficiently calculate the prefix sum.
For example, to calculate the prefix and a[0] + a[1] + a[2], we only need to do a few simple search and accumulation operations in the Fenwick Tree.

Things to note

Fenwick Tree can only efficiently handle prefix and query and single point update operations, and may not be applicable for other types of interval query and update operations.
When implementing Fenwick Tree, you need to pay attention to the offset of the array index (usually starting at 1 instead of 0) to simplify operations and avoid out-of-bounds issues.

Fenwick tree python implementation example

Fenwick Tree (also known as Binary Indexed Tree) is a data structure used to efficiently calculate prefix sum (Prefix Sum) that can be inserted, queryed, and updated in O(log n) time.

Here is a Python code example that implements the Fenwick Tree algorithm:

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

    # Update operation: Add delta to the element at the index i position    def update(self, i, delta):
        while i &lt;= :
            [i] += delta
            i += i &amp; -i

    # Query operation: Calculate the sum of the previous i elements    def query(self, i):
        res = 0
        while i &gt; 0:
            res += [i]
            i -= i &amp; -i
        return res

    # Calculate the sum of intervals [i, j]    def range_query(self, i, j):
        return (j) - (i-1)

Example of usage:

fenwick_tree = FenwickTree(10)
fenwick_tree.update(1, 2)
fenwick_tree.update(3, -1)
fenwick_tree.update(5, 5)

print(fenwick_tree.range_query(1, 5))  # Output: 6print(fenwick_tree.range_query(3, 7))  # Output：4

In the above code,FenwickTreeThe constructor of the class accepts an integer parameter n, indicating the size of the Fenwick Tree.

updateMethod is used to update an element in the Fenwick Tree
queryMethod is used to calculate the sum of the previous i elements
range_queryMethod is used to calculate the sum of intervals [i, j]

When using Fenwick Tree, you can make appropriate modifications according to actual needs.

For example:

CanupdateThe method is modified to set the element at the index i position to delta instead of adding delta.
Advanced applications also include calculating the number of inverse pairs, calculating the sum of inverse pairs, and so on.

Summarize

The above is personal experience. I hope you can give you a reference and I hope you can support me more.