Fenwick tree, also known as Binary Indexed Tree is data structure which is commonly used for range problems like getting sum of a range…