Range product (Binary Index Tree)

 arr = [1,2,3,4,5,6,7]. return the sub array product [i, j].

https://iq.opengenus.org/fenwick-tree-range-product/

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83

import java.util.*; public class Main { public static void main(String[] args) { System.out.println("Hello world"); RangeProduct rp = new RangeProduct(new int[]{1,2,3,4,5,6,7}); rp.buildBIT(); rp.print(); //System.out.println(rp.getPrefixProd(5)); System.out.println(rp.getRangeProd(1, 3)); } } class RangeProduct{ int[] arr; int n; int[] bit; RangeProduct(int[] _arr){ arr = _arr; n = arr.length; } int getParent(int x){ return x - (x&(-x)); } int getNext(int x){ return x + (x&(-x)); } //nlogn void buildBIT(){ bit = new int[n+1]; Arrays.fill(bit, 1); for(int i=1; i<=n; ++i){ int v = arr[i-1]; int j = i; while(j<=n){ bit[j] *= v; j = getNext(j); } } } int getPrefixProd(int i){ i++; int prod = 1; while(i>0){ prod *= bit[i]; i = getParent(i); } return prod; } int getRangeProd(int i, int j){ int prodj = getPrefixProd(j); int prodi = i==0 ? 1 : getPrefixProd(i-1); if(prodi!=0) return prodj/prodi; j++; int parent = getParent(j); int prod = 1; while(parent>=i){ if(bit[j]==0) return 0; prod *= bit[j]; j = parent; parent = getNext(j); } while(j>i){ if(arr[j-1]==0) return 0; prod*=arr[j-1]; j--; } return prod; } void print(){ System.out.println(Arrays.toString(bit)); } }