Segment Tree Sum with Lazy Update

public class SegmentTreeSum {

private static int[] arr = {1,9,2,3,5,8,90,1,2,88};

private static Node[] stArr;

private static int[] lazy;

private static void update(int root,int low,int high,int diff) {

if(root>=stArr.length) return;

Node n = stArr[root];

//no intersection

if(low > n.r || high < n.l) {

return;

}

if(lazy[root] > 0) {

nonLazyUpdate(root,lazy[root]);

}

//n is contained between low & high

if(n.l >= low && n.r <= high) {

int totalDiff = (n.r - n.l + 1)*diff;

n.val += totalDiff;

updateParents(root,totalDiff);

int left = root*2+1;

int right = root*2+2;

if(left < stArr.length) lazy[left] = diff;

if(right < stArr.length) lazy[right] = diff;

return;

}

//low <= n.r && high >= n.l

update(root*2+1,low,high,diff);

update(root*2+2,low,high,diff);

}

private static void nonLazyUpdate(int root, int diff) {

if(root >= stArr.length) return;

Node n = stArr[root];

if(n==null) return;

n.val += diff*(n.r - n.l + 1);

lazy[root] = 0;

int leftChild = 2*root+1;

int rightChild = 2*root+2;

if(leftChild < stArr.length && lazy[leftChild] > 0) nonLazyUpdate(leftChild, lazy[leftChild]);

if(rightChild < stArr.length && lazy[rightChild] > 0) nonLazyUpdate(rightChild, lazy[rightChild]);

nonLazyUpdate(leftChild, diff);

nonLazyUpdate(rightChild, diff);

}

private static void updateParents(int root, int totalDiff) {

if(root==0) return;

int parent = (root - 1)/2;

Node n = stArr[parent];

n.val += totalDiff;

updateParents(parent,totalDiff);

}

private static int query(int root,int low,int high) {

//System.out.println("query");

if(root>=stArr.length) return 0;

Node n = stArr[root];

if(lazy[root] > 0) {nonLazyUpdate(root, lazy[root]);}

//no intersection

if(low > n.r || high < n.l) {

return 0;

}

//n is contained between low & high

if(n.l >= low && n.r <= high) {

return n.val;

}

//low <= n.r && high >= n.l

int l_sum = query(root*2+1,low,high);

int r_sum = query(root*2+2,low,high);

int sum = l_sum + r_sum;

return sum;

}

private static void construct(int root,int low,int high) {

if(high<low) return;

if(root>=stArr.length) return;

Node n = new Node(low,high);

stArr[root] = n;

if(low==high) { n.val = arr[low]; return;}

int mid = low + (high-low)/2;

construct(2*root+1,low,mid);

construct(2*root+2,mid+1,high);

Node left = stArr[2*root+1];

Node right = stArr[2*root+2];

int lval  = left!=null?left.val:0;

int rval  = right!=null?right.val:0;

n.val = lval + rval;

}

public static void main(String[] args) {

int stlen = (int) Math.ceil(Math.log(arr.length*1l)/Math.log(2l)) + 1;

stArr = new Node[(int)( Math.pow(2, stlen) - 1)];

lazy = new int[stArr.length];

construct(0,0, arr.length-1);

System.out.println(query(0,0,4));

update(0,0,9,1);

update(0,0,4,1);

update(0,1,1,1);

System.out.println(query(0,0,4));

}

}

class NodeS {

int l;

int r;

int val;

public NodeS(int l,int r) {

this.l = l;

this.r = r;

}

}

Segment Tree For Min Query Java

public class SegmentTreeMin {

private static int[] arr = {1,9,2,3,5,8,90,1,2,88};

private static Node[] stArr;

private static int query(int root,int low,int high) {

//System.out.println("query");

if(root>=stArr.length) return -1;

Node n = stArr[root];

//no intesection

if(low > n.r || high < n.l) {

return -1;

}

//n is contained between low & high

if(n.l >= low && n.r <= high) {

return n.val;

}

//low <= n.r && high >= n.l

int l_ind = query(root*2+1,low,high);

int r_ind = query(root*2+2,low,high);

int min = Integer.MAX_VALUE;

int min_index = -1;

if(l_ind > -1) {min = arr[l_ind];min_index = l_ind;}

if(r_ind > -1 && arr[r_ind] < min) {min = arr[r_ind];min_index = r_ind;}

return min_index;

}

private static void construct(int root,int low,int high) {

if(high<low) return;

if(root>=stArr.length) return;

Node n = new Node(low,high);

stArr[root] = n;

if(low==high) { n.val = low; return;}

int mid = low + (high-low)/2;

construct(2*root+1,low,mid);

construct(2*root+2,mid+1,high);

Node left = stArr[2*root+1];

Node right = stArr[2*root+2];

int lval  = left!=null?arr[left.val]:Integer.MAX_VALUE;

int rval  = right!=null?arr[right.val]:Integer.MAX_VALUE;

if(lval<rval) n.val = left.val; else n.val = right.val;

}

public static void main(String[] args) {

int stlen = (int) Math.ceil(Math.log(arr.length*1l)/Math.log(2l)) + 1;

stArr = new Node[(int)( Math.pow(2, stlen) - 1)];

construct(0,0, arr.length-1);

int min_index = query(0,5,7);

int minVal = min_index > -1?arr[min_index]:-1;

System.out.println(minVal);

/*for(int i=0;i<stArr.length;i++) {

Node n = stArr[i];

if(n!=null) {

System.out.println(i+" "+n.l+" "+n.r+" "+n.val);

}

}*/

}

}

class Node {

int l;

int r;

int val;

public Node(int l,int r) {

this.l = l;

this.r = r;

}

}

java heap

import java.util.Arrays;

public class HeapTest {

public static void main(String[] args) {

int[] heap = { 1, 9, 8, 2, 11, 90, 1, 34, 32, 21, 43, 34, 56, 78, 89, 87, 69 };

int heapSize = heap.length;

System.out.println("before heap creation "+Arrays.toString(heap));

createHeap(heap,heapSize);

System.out.println("after heap creation "+Arrays.toString(heap));

heapSort(heap, heapSize);

System.out.println("after heap sort "+Arrays.toString(heap));

}

private static void createHeap(int[] heap,int heapSize) {

for (int i = 1; i < heapSize; i++) {

bubble_up(heap, i);

}

}

private static void heapSort(int[] heap,int heapSize) {

while (heapSize >= 1) {

extract(heap, heapSize);

--heapSize;

}

}

private static int extract(int[] arr, int len) {

if (len == 0)

return -1;

int max = arr[0];

swap(arr, 0, len - 1);

bubble_down(arr, 0, len - 2);

return max;

}

private static void swap(int[] a, int i, int j) {

int tmp = a[i];

a[i] = a[j];

a[j] = tmp;

}

private static void bubble_down(int[] a, int root, int last_index) {

if (last_index <= 0)

return;

int l = 2 * root + 1;

if (l > last_index)

return;

int r = 2 * root + 2;

int new_parent = l;

if (r <= last_index && a[r] > a[l])

new_parent = r;

if (a[root] < a[new_parent]) {

swap(a, root, new_parent);

bubble_down(a, new_parent, last_index);

}

}

private static void bubble_up(int[] heap, int last_index) {

if (last_index == 0)

return;

int parent = (last_index - 1) / 2;

if (heap[last_index] > heap[parent]) {

swap(heap, last_index, parent);

bubble_up(heap, parent);

}

}

}

java rmq using sparse table algorithm

int[][] m = process(a);

query(i,j,m,a);

public static int query(int i,int j,int[][] m, int[] a) {

int k = binlog(j-i+1);

return Math.min(a[m[i][k]], a[m[j+1-(1<<k)][k]]);

}

public static int binlog( int bits ) // returns 0 for bits=0

{

   int log = 0;

   if( ( bits & 0xffff0000 ) != 0 ) { bits >>>= 16; log = 16; }

   if( bits >= 256 ) { bits >>>= 8; log += 8; }

   if( bits >= 16  ) { bits >>>= 4; log += 4; }

   if( bits >= 4   ) { bits >>>= 2; log += 2; }

   return log + ( bits >>> 1 );

}

private static int[][] process(int[] a) {

int n = a.length;

int[][] m = new int[n][binlog(n)+1];

 //initialize M for the intervals with length 1

     for (int i = 0; i < n; i++)

         m[i][0] = i;

 //compute values from smaller to bigger intervals

     for (int j = 1; 1 << j <= n; j++)

         for (int i = 0; i + (1 << j) - 1 < n; i++)

             if (a[m[i][j - 1]] < a[m[i + (1 << (j - 1))][j - 1]])

                 m[i][j] = m[i][j - 1];

             else

                 m[i][j] = m[i + (1 << (j - 1))][j - 1];

     return m;

 }  

java rmq using sqrt appoach - range minimum query using squre root approach

int[] a;

int bucketSize = (int) Math.ceil(Math.sqrt(a.length));

int[] m = preProcess(a,bucketSize);

               int ans = query(i,j,m,a,bucketSize);

private static int query(int i, int j, int[] m, int[] a, int bucketSize) {

int curr_min = a[i];

if(j - i +1 < 2*bucketSize) {

for(int k=i;k<=j;k++) {

curr_min = Math.min(curr_min, a[k]);

}

return curr_min;

}

int seg_start = (i + bucketSize - 1) / bucketSize;

int seg_end = (j+1)/bucketSize - 1;

curr_min = a[m[seg_start]];

for(int k=seg_start;k<=seg_end;k++)

curr_min = Math.min(curr_min,a[m[k]]);

for(int k=i;k<seg_start*bucketSize;k++)

curr_min = Math.min(curr_min,a[k]);

for(int k=j;k>=(seg_end+1)*bucketSize;k--)

curr_min = Math.min(curr_min,a[k]);

return curr_min;

}

private static int[] process(int[] a, int bucketSize) {

int[] m = new int[(int)Math.ceil(a.length*1.0/bucketSize*1.0)];

int count = 0;

for (int i = 0; count < a.length; i++) {

int min = a[count];

m[i] = count;

for (int j = 0; j < bucketSize && count < a.length; j++) {

if (a[count] < min) {

min = a[count];

m[i] = count;

}

++count;

}

}

return m;

}

aws cli s3

aws configure

copy bucket to local
aws s3 sync s3://bucket-name .

copy local folder to s3 bucket
aws s3 sync folder/ s3://folder