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

/**
 * 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;
	}
}