SegmentTree.java

class SegmentTree { 

    public int modifyOperation(int x, int y) {
      return x + y;
    }

    public int queryOperation(int leftValue, int rightValue) {
      return Math.max(leftValue, rightValue);
    }

    public int deltaEffectOnSegment(int delta, int segmentLength) {
      if (delta == getNeutralDelta()) return getNeutralDelta();
      return delta;
    }

    public int getNeutralDelta() {
      return 0;
    }

    public int getInitValue() {
      return 0;
    }

    // generic code
    public int n;
    public int[] value;
    public int[] delta; // delta[i] affects value[i], delta[2*i+1] and delta[2*i+2]

    protected int joinValueWithDelta(int value, int delta) {
      if (delta == getNeutralDelta()) return value;
      return modifyOperation(value, delta);
    }

    protected int joinDeltas(int delta1, int delta2) {
      if (delta1 == getNeutralDelta()) return delta2;
      if (delta2 == getNeutralDelta()) return delta1;
      return modifyOperation(delta1, delta2);
    }

    protected void pushDelta(int root, int left, int right) {
      value[root] = joinValueWithDelta(value[root], deltaEffectOnSegment(delta[root], right - left + 1));
      delta[2 * root + 1] = joinDeltas(delta[2 * root + 1], delta[root]);
      delta[2 * root + 2] = joinDeltas(delta[2 * root + 2], delta[root]);
      delta[root] = getNeutralDelta();
    }

    public SegmentTree(int n) {
      this.n = n;
      value = new int[4 * n];
      delta = new int[4 * n];
      init(0, 0, n - 1);
    }

    public void init(int root, int left, int right) {
      if (left == right) {
        value[root] = getInitValue();
        delta[root] = getNeutralDelta();
      } else {
        int mid = (left + right) >> 1;
        init(2 * root + 1, left, mid);
        init(2 * root + 2, mid + 1, right);
        value[root] = queryOperation(value[2 * root + 1], value[2 * root + 2]);
        delta[root] = getNeutralDelta();
      }
    }

    public int query(int from, int to) {
      return query(from, to, 0, 0, n - 1);
    }

    int query(int from, int to, int root, int left, int right) {
      if (from == left && to == right)
        return joinValueWithDelta(value[root], deltaEffectOnSegment(delta[root], right - left + 1));
      pushDelta(root, left, right);
      int mid = (left + right) >> 1;
      if (from <= mid && to > mid)
        return queryOperation(
            query(from, Math.min(to, mid), root * 2 + 1, left, mid),
            query(Math.max(from, mid + 1), to, root * 2 + 2, mid + 1, right));
      else if (from <= mid)
        return query(from, Math.min(to, mid), root * 2 + 1, left, mid);
      else if (to > mid)
        return query(Math.max(from, mid + 1), to, root * 2 + 2, mid + 1, right);
      else
        throw new RuntimeException("Incorrect query from " + from + " to " + to);
    }

    public void modify(int from, int to, int delta) {
      modify(from, to, delta, 0, 0, n - 1);
    }

    public void modify(int from, int to, int delta, int root, int left, int right) {
      if (from == left && to == right) {
        this.delta[root] = joinDeltas(this.delta[root], delta);
        return;
      }
      pushDelta(root, left, right);
      int mid = (left + right) >> 1;
      if (from <= mid)
        modify(from, Math.min(to, mid), delta, 2 * root + 1, left, mid);
      if (to > mid)
        modify(Math.max(from, mid + 1), to, delta, 2 * root + 2, mid + 1, right);
      value[root] = queryOperation(
          joinValueWithDelta(value[2 * root + 1], deltaEffectOnSegment(this.delta[2 * root + 1], mid - left + 1)),
          joinValueWithDelta(value[2 * root + 2], deltaEffectOnSegment(this.delta[2 * root + 2], right - mid)));
    }
  }