Class FenwickTree<T>

A Fenwick Tree (binary indexed tree) implementation for prefix sum.

Inheritance
Object
FenwickTree<T>
Implements
Inherited Members
Namespace: Advanced.Algorithms.DataStructures
Assembly: Advanced.Algorithms.dll
Syntax
public class FenwickTree<T> : IEnumerable<T>, IEnumerable
Type Parameters
Name Description
T

Constructors

| Improve this Doc View Source

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

| Improve this Doc View Source

GetEnumerator()

Declaration
public IEnumerator<T> GetEnumerator()
Returns
Type Description
IEnumerator<T>
| Improve this Doc View Source

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
Type Description
T

Explicit Interface Implementations

| Improve this Doc View Source

IEnumerable.GetEnumerator()

Declaration
IEnumerator IEnumerable.GetEnumerator()
Returns
Type Description
IEnumerator

Implements