fork(1) download
copy 
  1. import java.util.*;
  2.  
  3. class SegmentTree {         
  4.   private int[] st, A;
  5.   private int n;
  6.   private int left (int p) { 
  7.   	return p << 1; 
  8.   }
  9.   private int right(int p) { 
  10.   	return (p << 1) + 1; 
  11.   }
  12.  
  13.   private void build(int p, int L, int R) {
  14.     if (L == R)                            
  15.       st[p] = L;                                         
  16.     else {                                
  17.       build(left(p) , L              , (L + R) / 2);
  18.       build(right(p), (L + R) / 2 + 1, R          );
  19.       int p1 = st[left(p)], p2 = st[right(p)];
  20.       st[p] = (A[p1] <= A[p2]) ? p1 : p2;
  21.   } }
  22.  
  23.   private int rmq(int p, int L, int R, int i, int j) {          
  24.     if (i >  R || j <  L) return -1; 
  25.     if (L >= i && R <= j) return st[p];              
  26.  
  27.  
  28.     int p1 = rmq(left(p) , L              , (L+R) / 2, i, j);
  29.     int p2 = rmq(right(p), (L+R) / 2 + 1, R          , i, j);
  30.  
  31.     if (p1 == -1) return p2;   
  32.     if (p2 == -1) return p1;                               
  33.     return (A[p1] <= A[p2]) ? p1 : p2; }          
  34.  
  35.   private int update_point(int p, int L, int R, int idx, int new_value) {
  36.     int i = idx, j = idx;
  37.     if (i > R || j < L)
  38.       return st[p];
  39.     if (L == i && R == j) {
  40.       A[i] = new_value; 
  41.       return st[p] = L;
  42.     }
  43.     int p1, p2;
  44.     p1 = update_point(left(p) , L              , (L + R) / 2, idx, new_value);
  45.     p2 = update_point(right(p), (L + R) / 2 + 1, R          , idx, new_value);
  46.     return st[p] = (A[p1] <= A[p2]) ? p1 : p2;
  47.   }
  48.  
  49.   public SegmentTree(int[] _A) {
  50.     A = _A; n = A.length;                   
  51.     st = new int[4 * n];
  52.     for (int i = 0; i < 4 * n; i++) st[i] = 0; 
  53.     build(1, 0, n - 1);                                  
  54.   }
  55.  
  56.   public int rmq(int i, int j) { return rmq(1, 0, n - 1, i, j); }
  57.  
  58.   public int update_point(int idx, int new_value) {
  59.     return update_point(1, 0, n - 1, idx, new_value); }
  60. }
  61.  
  62. class Main {
  63.   public static void main(String[] args) {
  64.     int[] A = new int[] { 18, 17, 13, 19, 15, 11, 20 }; 
  65.     SegmentTree st = new SegmentTree(A);
  66.  
  67.     System.out.printf("              idx    0, 1, 2, 3, 4,  5, 6\n");
  68.     System.out.printf("              A is {18,17,13,19,15, 11,20}\n");
  69.     System.out.printf("RMQ(1, 3) = %d\n", st.rmq(1, 3)); // answer = index 2
  70.     System.out.printf("RMQ(4, 6) = %d\n", st.rmq(4, 6)); // answer = index 5
  71.     System.out.printf("RMQ(3, 4) = %d\n", st.rmq(3, 4)); // answer = index 4
  72.     System.out.printf("RMQ(0, 0) = %d\n", st.rmq(0, 0)); // answer = index 0
  73.     System.out.printf("RMQ(0, 1) = %d\n", st.rmq(0, 1)); // answer = index 1
  74.     System.out.printf("RMQ(0, 6) = %d\n", st.rmq(0, 6)); // answer = index 5
  75.  
  76.     System.out.printf("              idx    0, 1, 2, 3, 4,  5, 6\n");
  77.     System.out.printf("Now, modify A into {18,17,13,19,15,100,20}\n");
  78.     st.update_point(5, 100);                  // update A[5] from 11 to 100
  79.     System.out.printf("These values do not change\n");
  80.     System.out.printf("RMQ(1, 3) = %d\n", st.rmq(1, 3));               // 2
  81.     System.out.printf("RMQ(3, 4) = %d\n", st.rmq(3, 4));               // 4
  82.     System.out.printf("RMQ(0, 0) = %d\n", st.rmq(0, 0));               // 0
  83.     System.out.printf("RMQ(0, 1) = %d\n", st.rmq(0, 1));               // 1
  84.     System.out.printf("These values change\n");
  85.     System.out.printf("RMQ(0, 6) = %d\n", st.rmq(0, 6));            // 5->2
  86.     System.out.printf("RMQ(4, 6) = %d\n", st.rmq(4, 6));            // 5->4
  87.     System.out.printf("RMQ(4, 5) = %d\n", st.rmq(4, 5));            // 5->4
  88.   }
  89. }
Success #stdin #stdout 0.04s 711168KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
              idx    0, 1, 2, 3, 4,  5, 6
              A is {18,17,13,19,15, 11,20}
RMQ(1, 3) = 2
RMQ(4, 6) = 5
RMQ(3, 4) = 4
RMQ(0, 0) = 0
RMQ(0, 1) = 1
RMQ(0, 6) = 5
              idx    0, 1, 2, 3, 4,  5, 6
Now, modify A into {18,17,13,19,15,100,20}
These values do not change
RMQ(1, 3) = 2
RMQ(3, 4) = 4
RMQ(0, 0) = 0
RMQ(0, 1) = 1
These values change
RMQ(0, 6) = 2
RMQ(4, 6) = 4
RMQ(4, 5) = 4
https://ideone.com/jDrFJ0
language:
Java (12.0.1)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!