Fenwick Tree

Never used this...there's a way to do it with just binary ops that's shorter to code. but this works too and is asymptotically as fast <syntaxhighlight line lang="java"> /**

* fenwick tree rather implemented with a heap rather than strict binary ops
* @author Kevin
*
*/

public class FenwickTree { double[] heap; /** * fenwick tree constructor * @param in the array of values */ public FenwickTree(double[] in){ heap=new double[Integer.highestOneBit(in.length)<<1]; for(int i=0;i<in.length;i++)operate(i,in[i],true); } /** * query or update the tree * @param index the index to query or update * @param value the value to change it to * @param update whether you want to update the tree or not * @return the value of the query or 0 if an update */ public double operate(int index, double value,boolean update) { int heapIndex=1,root=heap.length>>1,delta=root; index++; if(index==0||index==heap.length)return 0; while(index!=root){ heapIndex<<=1; if(index>root){ value-=heap[heapIndex>>1]; heapIndex++; root+=delta; } delta>>=1; root-=delta; } double diff=value-heap[heapIndex]; if(!update)return -1*diff; diff+=operate(index-2,0,false); heap[heapIndex]+=diff; while(heapIndex!=1){ if((heapIndex&1)==0)heap[heapIndex>>1]+=diff; heapIndex>>=1; } return 0; } }