FenwickTree (Encodings)

FenwickTree Module

Namespace: Encodings
Assembly: Encodings.dll

 A purely functional Fenwick tree (binary indexed tree) parameterized by
 an associative combining operation.

 The tree stores partial aggregates over an array of n values, supporting:
   - point update   : O(log n)
   - prefix query   : O(log n)
   - range query    : via prefix difference when the combine has an inverse

 The index sets used by the Bravyi-Kitaev encoding (update, parity,
 occupation, remainder) all fall out naturally from the Fenwick tree
 structure, making this a good foundation for the BK transform.

Types

Type	Description
FenwickTree<'a>	A Fenwick tree over values of type 'a. 'combine' must be associative: combine (combine a b) c = combine a (combine b c) 'identity' must be a left/right identity for combine.

Functions and values

Function or value	Description
`ancestors n k` Full Usage: `ancestors n k` Parameters: n : `int` k : `int` Returns: `int seq`	Walk from k toward the root by adding the lowest set bit. Returns the sequence of 1-based ancestor indices (excluding k itself). n : `int` k : `int` Returns: `int seq`
`build combine identity n f` Full Usage: `build combine identity n f` Parameters: combine : `'a -> 'a -> 'a` identity : `'a` n : `int` f : `int -> 'a` Returns: `FenwickTree<'a>`	Build a Fenwick tree of size n from a point-value function f, where f returns the raw value at 0-based index i. combine : `'a -> 'a -> 'a` identity : `'a` n : `int` f : `int -> 'a` Returns: `FenwickTree<'a>`
`descendants k` Full Usage: `descendants k` Parameters: k : `int` Returns: `int seq`	Walk from k toward the leaves by clearing the lowest set bit. Returns the sequence of 1-based descendant indices (excluding k itself), stopping at the "left wall" of k's subtree. k : `int` Returns: `int seq`
`empty combine identity n` Full Usage: `empty combine identity n` Parameters: combine : `'a -> 'a -> 'a` identity : `'a` n : `int` Returns: `FenwickTree<'a>`	Create an empty (all-identity) Fenwick tree of size n. combine : `'a -> 'a -> 'a` identity : `'a` n : `int` Returns: `FenwickTree<'a>`
`lsb k` Full Usage: `lsb k` Parameters: k : `^a` Returns: `^a` Modifiers: inline Type parameters: ^a	Lowest set bit of k (e.g. lsb 6 = 2, lsb 8 = 8). k : `^a` Returns: `^a`
`occupationSet j` Full Usage: `occupationSet j` Parameters: j : `int` Returns: `Set<int>`	Occupation set Occ(j): the set of indices in j's subtree that together determine element j's value. { j } ∪ { descendants of j+1 in 1-based Fenwick } Returns 0-based indices. j : `int` Returns: `Set<int>`
`ofArray combine identity values` Full Usage: `ofArray combine identity values` Parameters: combine : `'a -> 'a -> 'a` identity : `'a` values : `'a array` Returns: `FenwickTree<'a>`	Build a Fenwick tree from an array of values. combine : `'a -> 'a -> 'a` identity : `'a` values : `'a array` Returns: `FenwickTree<'a>`
`paritySet j` Full Usage: `paritySet j` Parameters: j : `int` Returns: `Set<int>`	Parity set P(j): the set of tree indices whose stored values contribute to the prefix aggregate of elements 0 .. (j-1). Returns 0-based indices. j : `int` Returns: `Set<int>`
`pointQuery tree j` Full Usage: `pointQuery tree j` Parameters: tree : `FenwickTree<'a>` j : `int` Returns: `'a`	Retrieve the single-element value at 0-based index j. Requires that 'combine' has a notion of "undo" or that we reconstruct from the tree structure. For a XOR / symmetric-difference tree this is exact. For a general tree, this walks the Fenwick descendants. tree : `FenwickTree<'a>` j : `int` Returns: `'a`
`prefixIndices k` Full Usage: `prefixIndices k` Parameters: k : `int` Returns: `int seq`	Walk by clearing the lowest set bit starting from k itself. Returns the 1-based prefix-contributing indices. k : `int` Returns: `int seq`
`prefixQuery tree j` Full Usage: `prefixQuery tree j` Parameters: tree : `FenwickTree<'a>` j : `int` Returns: `'a`	Compute the prefix aggregate of elements 0 .. j (0-based, inclusive). tree : `FenwickTree<'a>` j : `int` Returns: `'a`
`remainderSet j` Full Usage: `remainderSet j` Parameters: j : `int` Returns: `Set<int>`	Remainder set R(j) = P(j) \ Occ(j). j : `int` Returns: `Set<int>`
`size tree` Full Usage: `size tree` Parameters: tree : `FenwickTree<'a>` Returns: `int`	The number of elements in the tree. tree : `FenwickTree<'a>` Returns: `int`
`symmetricDifference a b` Full Usage: `symmetricDifference a b` Parameters: a : `Set<'b>` b : `Set<'b>` Returns: `Set<'b>`	Symmetric difference of two sets. a : `Set<'b>` b : `Set<'b>` Returns: `Set<'b>`
`update tree j delta` Full Usage: `update tree j delta` Parameters: tree : `FenwickTree<'a>` j : `int` delta : `'a` Returns: `FenwickTree<'a>`	Return a new Fenwick tree with the value at 0-based index j combined with delta: tree[j] <- combine tree[j] delta tree : `FenwickTree<'a>` j : `int` delta : `'a` Returns: `FenwickTree<'a>`
`updateSet j n` Full Usage: `updateSet j n` Parameters: j : `int` n : `int` Returns: `Set<int>`	Update set U(j): the set of ancestor indices that store partial aggregates including element j. These are the nodes that need updating when element j changes. Returns 0-based index set, excluding j itself. j : `int` n : `int` Returns: `Set<int>`