Tuesday, September 27, 2016

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

Monday, September 26, 2016

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);
}
}
}

Wednesday, September 21, 2016

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

Thursday, September 15, 2016

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

Blog Archive