Fenwick Tree and its Application in Solving the Sum of Subsequence

Abstract — In this paper, through analysis of the Fenwick Tree(for short, FT), we give the basic form of tree structure under the specified number of elements. Proving theories of the FT’s operations, we realize the FT’s operational algorithms and provide the method to achieve the sum of subsequence by FT, whose time complexity is 2(log)O n. The experimental program is executed and its result reveals that the consuming time of achieving the sum of subsequence by FT is far below the time of two commonly methods(denoted as, M1 and M2), and its average running velocity is about 182 times faster than M1’s and 82 times faster than M2’s