fork download
copy 
  1. public abstract class SegmentsTree {
  2.  
  3.     public abstract int defaultDelta();
  4.     public abstract int operation(int a, int b);
  5.     public abstract int defaultValue();
  6.     public abstract void change(int v, int delta);
  7.     protected int[] func;
  8.     protected int[] delta;
  9.     protected int[] left;
  10.     protected int[] right;
  11.     protected int size;
  12.  
  13.     public SegmentsTree(int[] a) {
  14.         size = a.length;
  15.         func = new int[4 * size + 2];
  16.         delta = new int[4 * size + 2];
  17.         left = new int[4 * size + 2];
  18.         right = new int[4 * size + 2];
  19.         build(0, size - 1, 1, a);
  20.     }
  21.     private void build(int left, int right, int v, int[] a) {
  22.         this.left[v] = left;
  23.         this.right[v] = right;
  24.         delta[v] = defaultDelta();
  25.         if (left == right) {
  26.             func[v] = a[left];
  27.         } else {
  28.             int middle = (left + right) >> 1;
  29.             build(left, middle, v << 1, a);
  30.             build(middle + 1, right, (v << 1) + 1, a);
  31.             func[v] = operation(func[v << 1], func[(v << 1) + 1]);
  32.         }
  33.     }
  34.     public void change(int left, int right, int delta) {
  35.         change(0, size - 1, left, right, 1, delta);
  36.     }
  37.     private void change(int lTree, int rTree, int left, int right, int v, int delta) {
  38.         if (rTree < left || right < lTree)
  39.             return;
  40.         push(v);
  41.         if (left <= lTree && rTree <= right) {
  42.             change(v, delta);
  43.         } else {
  44.             int middle = (lTree + rTree) >> 1;
  45.             change(lTree, middle, left, right, v << 1, delta);
  46.             change(middle + 1, rTree, left, right, (v << 1) + 1, delta);
  47.             func[v] = operation(func[v << 1], func[(v << 1) + 1]);
  48.         }
  49.     }
  50.     public int get(int left, int right) {
  51.         return get(0, size - 1, left, right, 1);
  52.     }
  53.  
  54.     private int get(int lTree, int rTree, int left, int right, int v) {
  55.         if (rTree < left || right < lTree)
  56.             return defaultValue();
  57.         push(v);
  58.         if (left <= lTree && rTree <= right)
  59.             return func[v];
  60.         else {
  61.             int middle = (lTree + rTree) >> 1;
  62.             return operation(
  63.                     get(lTree, middle, left, right, v << 1),
  64.                     get(middle + 1, rTree, left, right, (v << 1) + 1)
  65.             );
  66.         }
  67.     }
  68.     private void push(int v) {
  69.         if (delta[v] != defaultDelta()) {
  70.             if ((v << 1) < func.length)
  71.                 change(v << 1, delta[v]);
  72.             if ((v << 1) + 1 < func.length)
  73.                 change((v << 1) + 1, delta[v]);
  74.             delta[v] = defaultDelta();
  75.         }
  76.     }
  77. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:1: error: class SegmentsTree is public, should be declared in a file named SegmentsTree.java
public abstract class SegmentsTree {
                ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/C6CKTH
language:
Java (12.0.1)
created:
10 years ago
visibility:
public

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!