|
| 1 | +import java.util.*; |
| 2 | +public class segment_tree1 { |
| 3 | + public static int min(int x, int y) { |
| 4 | + //return Math.min(x, y); |
| 5 | + return (x < y) ? x : y; |
| 6 | + } |
| 7 | + public static final int NO_VALUE = 0; |
| 8 | + public static int div(int a,int b) { |
| 9 | + return (int) Math.floor(a/b); |
| 10 | + } |
| 11 | + public static int calc_half1(int x,int y) { |
| 12 | + return div((y-x) - 1,2); |
| 13 | + } |
| 14 | + public static int calc_half2(int x,int y) { |
| 15 | + return div((y-x),2) + 1; |
| 16 | + } |
| 17 | + public static int getMid(int s, int e) { |
| 18 | + return s + (e - s) / 2; |
| 19 | + } |
| 20 | + public static int getMaxSize(int x) { |
| 21 | + return 2 * (int) Math.pow(2, x) - 1; |
| 22 | + } |
| 23 | + public static int pow2(int x) { |
| 24 | + return (int) Math.pow(2, x); |
| 25 | + } |
| 26 | + public static int[] st; |
| 27 | + public static int[] segmenttree(int[] arr) { |
| 28 | + st = new int[getMaxSize(arr.length)]; |
| 29 | + int n = arr.length; |
| 30 | + recur_st(arr,0,n-1,0); |
| 31 | + return st; |
| 32 | + } |
| 33 | + static int times_recuron = 0; |
| 34 | + public static int recur_st(int[] arr,int a,int b,int c) { |
| 35 | + times_recuron ++; |
| 36 | + if(times_recuron>1000) { |
| 37 | + return 0; |
| 38 | + } |
| 39 | + if(a==b) { |
| 40 | + st[c] = arr[a]; |
| 41 | + return arr[a]; |
| 42 | + } |
| 43 | + int mid = getMid(a, b); |
| 44 | + st[c] = recur_st(arr,a, mid, c * 2 + 1) + recur_st(arr, mid + 1, b, c * 2 + 2); |
| 45 | + return st[c]; |
| 46 | + } |
| 47 | + public static int getsum(int a, int b, int c, int d, int e){ |
| 48 | + if (c <= a && d >= b) |
| 49 | + return st[e]; |
| 50 | + if (b < c || a > d) |
| 51 | + return 0; |
| 52 | + int mid = getMid(a, b); |
| 53 | + return getsum(a, mid, c, d, 2 * e + 1) + getsum(mid + 1, b, c, d, 2 * e + 2); |
| 54 | + } |
| 55 | + public static int recursionRMQ(int a, int b, int c, int d, int index){ |
| 56 | + if (c <= a && d >= b) |
| 57 | + return st[index]; // Lookup when done |
| 58 | + if (b < c || a > d) |
| 59 | + return Integer.MAX_VALUE; // This is my infinite value |
| 60 | + int mid = getMid(a, b); |
| 61 | + return min(recursionRMQ(a, mid, c, d, 2 * index + 1), |
| 62 | + recursionRMQ(mid + 1, b, c, d, 2 * index + 2)); |
| 63 | + } |
| 64 | + public static int RMQ(int n, int a, int b) |
| 65 | + { |
| 66 | + if (b > n - 1 || a > b || a < 0 ) { |
| 67 | + System.out.println("input not valid"); |
| 68 | + return -1; |
| 69 | + } |
| 70 | + |
| 71 | + return recursionRMQ(0, n - 1, a, b, 0); |
| 72 | + } |
| 73 | + public static void main(String[] args) { |
| 74 | + System.out.println("Self Test segement tree"); |
| 75 | + System.out.println("From 0 to 6: "+calc_half1(0,6)); |
| 76 | + //int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}; |
| 77 | + //int[] arr = {1,2,3,4,5,6}; |
| 78 | + //int[] arr ={1, 3, 5, 7, 9, 11}; |
| 79 | + //System.out.println(1 << 2); |
| 80 | + int[] arr = {0,5,2,5,4,3,1,6,3}; |
| 81 | + System.out.println(Arrays.toString(segmenttree(arr))); |
| 82 | + System.out.println("RMQ: "+RMQ(arr.length, 2,7)); |
| 83 | + } |
| 84 | + |
| 85 | +} |
0 commit comments