Segment Tree with Lazy Propogation

SegmentTree.java

//For theory refer: https://www.hackerearth.com/practice/notes/segment-tree-and-lazy-propagation/ 

public class SegmentTree {
	
	private Node[] heap;
	private int[] array;
	private int size;
	
	/*********************************************
	 * TREE CONSTRUCTION
	 *********************************************/
	
	//Node of a heap tree represnts a range of the array
	// with bounds: [n.from, n.to]
	class Node {
        int sum;
        int min;
        
        //Here We store the value that will be propagated lazily
        Integer pendingVal = null;
        int from;
        int to;

        int size() {
            return to - from + 1;
        }

    }
	
	public SegmentTree(int[] array){
		this.array = Arrays.copyOf(array, array.length);
		size = (int) (2*Math.pow(2.0, Math.floor((Math.log((double) array.length) / Math.log(2.0)) + 1)));
		heap = new Node[size];
		build(1,0,array.length);
	}
	
	private void build(int v, int from, int size){
		heap[v]= new Node();
		heap[v].from = from;
		heap[v].to = from+size-1;
		
		if(size==1){
			heap[v].sum=array[from];
			heap[v].min=array[from];
		} else {
			//build childs - decreasing the size to 1
			build(2*v,from,size/2);
			build(2*v+1,from+size/2,size-size/2);
			
			//constructing the sum array after coming back from recursive stack
			heap[v].sum = heap[2*v].sum+heap[2*v+1].sum;
			heap[v].min = Math.min(heap[2*v].min, heap[2*v+1].min);
		}
		
	}
	
	/*****************************************
	 * HELPER FUNCTIONS
	 *****************************************/
	
	//Propogate temporal values to children
	//Freshly created updates are propogated to children
	//In a lazy manner
	
	private void propogate(int v){
		Node n = heap[v];
		
		if(n.pendingVal!=null){
			change(heap[2*v],n.pendingVal);
			change(heap[2*v+1],n.pendingVal);
			n.pendingVal=null;
		}
	}
	
	//Saving the temporal values that propogate lazily
	//transfered temporal values from parent are saved 
	//temporarily in the child nodes
	
	private void change(Node n, int value){
		n.pendingVal = value;
		n.sum = n.size()*value;
		n.min = value;
		array[n.from]=value;
	}
	
	//If this range contains that range
	private boolean contains(int from1, int to1, int from2, int to2){
		return from2>=from1 && to2<=to1;
	}
	
	private boolean intersects(int from1, int to1, int from2, int to2){
		return (from1<=from2&& to1>=from2)||(from1>=from2 && from1<=to2);
	}
	
	
	/*****************************************
	 * RANGE SUM QUERY - O(log(n))
	 *****************************************/
	
	public int rangeSum(int from, int to){
		return rangeSum(1,from,to);
	}
	
	public int rangeSum(int v, int from, int to){
		
		Node n = heap[v];
		
		//If a range update is performed that contains
		//this node, you can infer the sum without goig down the tree
		
		if(n.pendingVal!=null&& contains(n.from,n.to,from,to)){
			return (to-from+1)*n.pendingVal;
		}
		
		if(contains(from,to,n.from,n.to)){
			return heap[v].sum;
		}
		
		if(intersects(from,to,n.from,n.to)){
			propogate(v);
			
			int leftSum = rangeSum(2*v,from,to);
			int rightSum = rangeSum(2*v+1,from, to);
			
			return leftSum+rightSum;
		}
		
		return 0;
		
	}
	
	/*****************************************
	 * RANGE MIN QUERY - O(log(n))
	 *****************************************/
	
	public int rangeMin(int from, int to){
		return rangeMin(1,from,to);
	}
	
	private int rangeMin(int v, int from, int to){
		
		Node n = heap[v];
		
		if(n.pendingVal!=null&& contains(n.from,n.to,from,to)){
			return n.pendingVal;
		}
		
		if(contains(from,to,n.from,n.to)){
			return heap[v].min;
		}
		
		if(intersects(from,to,n.from,n.to)){
			propogate(v);
			
			int leftMin = rangeMin(2*v,from,to);
			int rightMin = rangeMin(2*v+1,from, to);
			
			return Math.min(leftMin, rightMin);
		}
		
		return Integer.MAX_VALUE;
		
	}
	
	
	/*****************************************
	 * RANGE UPDATE IMPLEMENTATION - O(log(n))
	 *****************************************/
	
	public void update(int from, int to, int value){
		update(1,from,to,value);
	}
	
	private void update(int v, int from, int to, int value){
		Node n = heap[v];
		
		//If the updating range contains the portion of the current node
		// Lazily update it - We donot update each position of the vector
		//but update only some temporal values into the node
		//such values into the Node will be propogated down to its children
		// only when they need to
		
		if(contains(from,to,n.from,n.to)){
			change(n,value);
		}
		
		if(n.size()==1) return;
		
		//Before keeping going down the tree, We need to propogate
		//the values that have been temporally/lazily saved into this node's children
		//So when we actually go down the values are updated properly
		
		if(intersects(from,to,n.from,n.to)){
			propogate(v);
			
			update(2*v,from,to,value);
			update(2*v+1,from,to,value);
			
			n.sum = heap[2*v].sum+heap[2*v+1].sum;
			n.min = Math.min(heap[2*v].min, heap[2*v+1].min);
			
		}
		
	}
	
	

}