I had never learnt Fenwick and never ever had the need to implement one because I would always say that Segment tree is better, this post made me learn Fenwick in order to prove a point (or disprove).

Problem to solve is given N numbers and 2 type of queries: type 0 means add r to lth number and type 1 means get sum from l to r inclusive.

I tried random cases and extreme cases (Q=N=10^5) and segment tree

In my computer I get:
1000 Extreme cases:
Total Segment tree: 14.434
Total Fenwick tree: 16.162

10000 random cases:
Total Segment tree: 21.677
Total Fenwick tree: 24.464

In code forces custom run I get (had to run less tests because it gets timed out):
300 Extreme cases:
Total Segment tree: 2.140
Total Fenwick tree: 1.423

2000 random cases:
Total Segment tree: 1.977
Total Fenwick tree: 1.446

Basically results are inconsistent. So, which one is better I guess it depends, either way, differences are minimal to the point where I/O would actually have more impact than the data structure.

My conclusion is Segment tree is better, simply because it can be easily modified to achieve other thing's which BIT doesn't seem to be able to.

In order to learn segment tree I would recommend to start with recursive (to understand it), and then iterative (how to optimize it).

My code: http://pastebin.com/fFRY5FQE

Note: I used the iterative implementation of segment tree, since obviously recursive is slower.

Maybe BIT Vs Segment tree :)

The final sentence contradicted to the other :p

just like the old saying:"Segment Tree can do everything BIT can do and can't do." But sometimes it is very difficult to code.