Class FenwickTree<T>
A Fenwick Tree (binary indexed tree) implementation for prefix sum.
Inheritance
FenwickTree<T>
Assembly: Advanced.Algorithms.dll
Syntax
public class FenwickTree<T> : IEnumerable<T>, IEnumerable
Type Parameters
Constructors
FenwickTree(T[], Func<T, T, T>)
constructs a Fenwick tree using the specified sum operation function.
Time complexity: O(nLog(n)).
Declaration
public FenwickTree(T[] input, Func<T, T, T> sumOperation)
Parameters
Type |
Name |
Description |
T[] |
input |
|
Func<T, T, T> |
sumOperation |
|
Methods
GetEnumerator()
Declaration
public IEnumerator<T> GetEnumerator()
Returns
PrefixSum(Int32)
Gets the prefix sum from 0 till the given end index.
Time complexity: O(log(n)).
Declaration
public T PrefixSum(int endIndex)
Parameters
Type |
Name |
Description |
Int32 |
endIndex |
|
Returns
Explicit Interface Implementations
IEnumerable.GetEnumerator()
Declaration
IEnumerator IEnumerable.GetEnumerator()
Returns
Implements