fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /**
  8.  * Created by green on 28.11.15.
  9.  */
  10.  
  11. import java.security.Key;
  12.  
  13. /**
  14.  * Created by green on 26.11.15.
  15.  */
  16.  
  17. interface SegmentedArray<T> {
  18.     /**
  19.      * <p>Get value by element index</p>
  20.      * @param index index of element.
  21.      * @return  Value of element with specified index.
  22.      */
  23.     T get(int index);
  24.  
  25.     /**
  26.      * <p>Set the same value for all elements in the specified index range</p>
  27.      * @param start the beginning index, inclusive.
  28.      * @param end the ending index, exclusive.
  29.      * @param value value for.
  30.      */
  31.     void set(int start, int end, T value);
  32.  
  33.     /**
  34.      * <p>Returns the index within this array of the first occurrence of the specified value,
  35.      * starting at the specified index. If no such value of k exists, then -1 is returned.</p>
  36.      * @param value the T-based value for which to search.
  37.      * @param fromIndex the index from which to start the search.
  38.      * @return the index within this array of the first occurrence of the element with specified value,
  39.      * starting at the specified index.
  40.      */
  41.      int indexOf(T value, int fromIndex);
  42.  
  43.     /**
  44.      * <p>Find minimum value in the specified indexes range</p>
  45.      * @param start the beginning index, inclusive.
  46.      * @param end the ending index, exclusive.
  47.      * @return Minimum value.
  48.      */
  49.      T minValue(int start, int end);
  50. }
  51.  
  52.  
  53. class CT <Value extends Comparable<Value>>  implements SegmentedArray<Value>{
  54.  
  55.     private class Node {
  56.         Value value;
  57.         int l, r;
  58.         Node left, right, father;
  59.         public Node (Value value, Node father, int l, int r) {
  60.             this.value = value;
  61.             this.left = this.right = null;
  62.             this.father = father;
  63.             this.l = l; this.r = r;
  64.         }
  65.     }
  66.  
  67.     private Node root;
  68.  
  69.     private Node add (Node node,Value value, Node father, int l, int r){
  70.         if (node == null){
  71.             Node newnode = new Node(value,father, l , r);
  72.             return newnode;
  73.         }
  74.         //int compareResultl = l.compareTo(node.l);
  75.         //int compareResultr = r.compareTo(node.r);
  76.         if(l > node.r){
  77.             node.right = add(node.right, value, node, l, r);
  78.         }else if(r < node.l){
  79.             node.left = add(node.left, value, node, l, r);
  80.         }else if(l >= node.l && r <= node.r){
  81.             if(l == node.l && r == node.r){
  82.                 node.value = value;
  83.                 return node;
  84.             }else if(l == node.l){
  85.                 node.right = add(node.right, node.value, node, r+1, node.r);
  86.                 node.value = value;
  87.                 node.r = r;
  88.             }else if(r == node.r){
  89.                 node.left = add(node.left, node.value, node, node.l, l-1);
  90.                 node.value = value;
  91.                 node.l = l;
  92.             }else{
  93.                 Node newnode = new Node(value,father, l , r);
  94.                 newnode.left = node.left;
  95.                 newnode.right = node.right;
  96.                 newnode.left = add(newnode.left, node.value, newnode, node.l, l-1);
  97.                 newnode.right = add(newnode.right, node.value, newnode, r+1, node.r);
  98.                 node = newnode;
  99.             }
  100.         }else if(l < node.l && r > node.r){
  101.             node.value = value;
  102.             node.l = l;
  103.             node.r = r;
  104.             node.left = delete(node.left, l, false);
  105.             node.right = delete(node.right, r, true);
  106.         }else if(l < node.l){
  107.             if(r == node.r){
  108.                 node.value = value;
  109.                 node.l = l;
  110.                 node.left = delete(node.left, l, false);
  111.             }else{
  112.                 node = add(node, node.value, father, r+1, node.r);
  113.                 node = add(node, value, father, l, r);
  114.             }
  115.         }else if (r > node.r) {
  116.             if (l == node.l) {
  117.                 node.value = value;
  118.                 node.r = r;
  119.                 node.right = delete(node.right, r, true);
  120.             } else {
  121.                 node = add(node, node.value, father, node.l, l - 1);
  122.                 node = add(node, value, father, l, r);
  123.             }
  124.         }
  125.         return node;
  126.     }
  127.  
  128.     public void set(int l, int r, Value value) {
  129.         root = add(root, value, null, l, r);
  130.     }
  131.     private Node delete(Node node, int d, Boolean side){
  132.         if(node == null) return null;
  133.         if(d < node.r && d > node.l){
  134.             node = add(node, node.value, node.father, node.l, d - 1);
  135.             node = delete(node, d, side);
  136.         }else if(d < node.l){
  137.             if(side)
  138.                 node.left = delete(node.left, d, side);
  139.             else {
  140.                 node = node.left;
  141.                 node = delete(node, d, side);
  142.             }
  143.         }else if(d > node.r){
  144.             if(side) {
  145.                 node = node.right;
  146.                 node = delete(node, d, side);
  147.             }else
  148.                 node.right = delete(node.right, d, side);
  149.         }else if(d == node.r){
  150.             if(side) {node = node.right;} else {node.right = null;node.r = d - 1;}
  151.         }else if(d == node.l){
  152.             if(side) {node.left = null;node.l = d + 1;} else {node = node.left;}
  153.         }
  154.         return node;
  155.     }
  156.  
  157.     private Value get(Node node, int index){
  158.         if(node == null) return null;
  159.         if(index > node.r)
  160.             return get(node.right, index);
  161.         else if (index < node.l)
  162.             return get(node.left, index);
  163.         else
  164.             return node.value;
  165.     }
  166.  
  167.     public Value get(int index) {
  168.         return get(root, index);
  169.     }
  170.  
  171.     private Value minimum(Value x, Value y){
  172.         if(x == null && y == null) return null;
  173.         else if(x == null) return y;
  174.         else if(y == null) return x;
  175.         else {
  176.             if (x.compareTo(y) == 1) return y;
  177.             else return x;
  178.         }
  179.     }
  180.  
  181.     private Value min(Node node, int start, int end){
  182.         if(node == null) return null;
  183.         if(end < node.l){
  184.             return min(node.left, start, end);
  185.         }else if (start > node.r){
  186.             return min(node.right, start, end);
  187.         }else{
  188.             Value v1 = null, v2 = null;
  189.             if(start < node.l) v1 = min(node.left, start, end);
  190.             if(end > node.r) v2 = min(node.right, start, end);
  191.             return minimum(v2, minimum(node.value, v1));
  192.         }
  193.     }
  194.  
  195.     public Value minValue(int start, int end){
  196.         return min(root, start, end);
  197.     }
  198.  
  199.     private Integer indexOf(Node node, Value value, int index){
  200.         if(node == null) return null;
  201.         if(index <= node.r) {
  202.             Integer v = null;
  203.             if(index < node.l){
  204.                 v = indexOf(node.left, value, index);
  205.                 if (v != null) return v;
  206.             }
  207.             if (value == node.value) return Math.max(node.l, index);
  208.             v = indexOf(node.right, value, index);
  209.             if (v != null) return v;
  210.         }
  211.         return indexOf(node.right, value, index);
  212.     }
  213.  
  214.     public int indexOf(Value value, int index){
  215.         return indexOf(root, value, index);
  216.     }
  217.  
  218.     private void print(Node node, int level) {
  219.         if (node != null) {
  220.             print(node.right,level+1);
  221.             for (int i=0;i<level;i++) {
  222.                 System.out.print("\t");
  223.             }
  224.             System.out.println(node.l + "-" + node.r + "->" + node.value);
  225.             print(node.left,level+1);
  226.         }
  227.     }
  228.  
  229.     public void print() {
  230.         print(root,0);
  231.     }
  232.  
  233. }
  234.  
  235.  
  236.  
  237. /* Name of the class has to be "Main" only if the class is public. */
  238. class Ideone
  239. {
  240. 	public static void main (String[] args) throws java.lang.Exception
  241. 	{
  242.         CT<Integer> tree = new CT<>();
  243.         long start, end;
  244.         start = System.nanoTime();
  245.         tree.set(50, 4566, 14);
  246.         //tree.set(130, 740, 29012);
  247.         //tree.set(1000, 1084, -2);
  248.         //tree.set(3006, 3070, 51);
  249.         end = System.nanoTime();//tree.set(50, 4566, 14);
  250.         System.out.println("Первый Set в BitSegmentedArray отрабатывает за " + (end - start) + " нс.");
  251.  
  252.         start = System.nanoTime();
  253.         Integer get = tree.get(111);
  254.         end = System.nanoTime();
  255.         System.out.println("Get в BitSegmentedArray отрабатывает за " + (end - start) + " нс.");
  256.         System.out.println(get);
  257.  
  258.         start = System.nanoTime();
  259.         tree.set(76, 830, 1);
  260.         end = System.nanoTime();
  261.         System.out.println("Второй Set в BitSegmentedArray отрабатывает за " + (end - start) + " нс.");
  262.         tree.set(60, 92, 0);
  263.  
  264.         start = System.nanoTime();
  265.         int minimum = tree.minValue(130, 1400);
  266.         end = System.nanoTime();
  267.         System.out.println("Min в BitSegmentedArray отрабатывает за " + (end - start) + " нс.");
  268.         System.out.println(minimum);
  269.         tree.print();
  270.     }
  271. }
Success #stdin #stdout 0.11s 320576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Gthвый Set в BitSegmentedArray отрабатывает за 423481 нс.
Get в BitSegmentedArray отрабатывает за 20142 нс.
14
Второй Set в BitSegmentedArray отрабатывает за 15228 нс.
Min в BitSegmentedArray отрабатывает за 31566 нс.
1
	831-4566->14
93-830->1
		60-92->0
	50-59->14
https://ideone.com/KEog4C
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!