Skip to content

Implement Clone and Debug for FenwickTree #145

Open
@NotLeonian

Description

@NotLeonian

Implement the Clone and Debug traits for FenwickTree.

For the Clone trait, it should be enough to add a Clone trait bound to T and write an explicit impl.

For the Debug trait, I think that discussion is needed regarding the output format.
Unlike Segtree and LazySegtree, FenwickTree does not have self.log.
Additionally, in a Fenwick Tree, the structure does not explicitly store all segments like a Segment Tree or Lazy Segment Tree. This difference causes gaps in the tree representation, making it problematic to use the same output format.

Therefore, I propose an output format that includes self.n, self.e, and the return values of the accum function for 1..=self.n.
For example, if self.n = 10, self.e = 0, and the array is [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], the output could be one of the following:

FenwickTree { n: 10, e: 0, accum: [0, 1, 3, 6, 10, 15, 21, 28, 36, 45] }
n: 10
e: 0
accum: 0        1       3       6       10      15      21      28      36      45

With this implementation, the required trait bounds for T are limited to Clone + Debug + std::ops::AddAssign<T>.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions