Implement Clone and Debug for FenwickTree

[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>.

[TonalidadeHidrica]

We may also accept the "alternate" flag (#) to adopt both.

[NotLeonian]

Thank you! That certainly sounds like a better approach.
By "both," do you mean both the output format similar to Segtree and LazySegtree and the format I proposed?
Or do you mean both of the two formats I proposed?

[TonalidadeHidrica]

That's what I obfuscated indeed 😜 There are two rooms and we need to discuss which to print for each of them.
Personally I think the following two would be a good choice:

• Printing it in a single line with the ordinary struct-like formatting, as shown in your first example.
• Printing it as an ASCII art like this, including as much information as possible. Showing the internal structure may help debugging when the user's Add implementation (or e) is wrong.

Tree:
|                                    28 |
|                6  |                   |
|      1  |         |      9  |         |      17 |
| 0  |    | 2  |    | 4  |    | 6  |    | 8  |    |
Accum:
| 0  | 1  | 3  | 6  | 10 | 15 | 21 | 28 | 36 | 45 |
Elem:
| 0  | 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9  |
Index:
| 0  | 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9  |

Alternatively, one may delegate the latter format to Display and keep Debug simple. In that case, only showing the internal array would be that without # and those including accum and elem would be #.

[NotLeonian]

I see, that makes a lot of sense.
The ASCII art-like representation seems really useful, though I do have some concerns about potential formatting issues.
Also, I agree that using the Display trait certainly makes it clearer and easier to understand, especially for users who aren’t familiar with the alternate flag.

If we go with the ASCII art-like format, it would be nice to update Segtree and LazySegtree as well to keep things consistent.

[koba-e964]

I disagree with implementing Display as Display is not implemented for standard containers such as Vec, HashMap and HashSet.

it is often preferable to only implement Display when there is a single most "obvious" way that values can be formatted as text.

https://doc.rust-lang.org/std/fmt/trait.Display.html

[TonalidadeHidrica]

Considering that this is not a library for public use but rather competitive-programming oriented, sometimes it may be good idea not follow the convention in standard Rust language. A notable example is that we allow arithmetic operations of modint against arbitrary integer types, which doesn't follow usual Rust philosophy. Of course, whether to provide the visualization feature via Display requires a thorough discussions, but in my opinion giving a chance of easy debugging in a short-handed way is not necessarily a bad idea.