@Test public void testRandomQueryAndRangeAddDelta() { Random r = new Random(); int N = 500; Integer[] in = new Integer[N]; for (int i = 0; i < N; i++) in[i] = r.nextInt(N) * 2 - N; SegmentTree<Integer> sumTree = new SegmentTree<>(in, (a, b) -> a + b, (a, b) -> { if (a == null) a = 0; return a + b; }, (ori, extra, st, ed) -> ori + (ed - st + 1) * extra); checkSum(in, sumTree); for (int j = 0; j < 5; j++) { for (int i = 0; i < 3; i++) { int k1 = r.nextInt(N), k2 = r.nextInt(N); int st = Math.min(k1, k2), ed = Math.max(k1, k2); int val = r.nextInt(N) * 2 - N; for (int k = st; k <= ed; k++) in[k] += val; sumTree.updateRange(st, ed, val); } checkSum(in, sumTree); } }
public void updateRange(int st, int ed, E e) { if (extraUpdater == null || extraMerger == null) throw new IllegalStateException("extraUpdater OR extraMerger should not be null in range update"); if (st < 0 || ed >= size || st > ed) throw new IllegalArgumentException("invalid range"); updateRange(0, 0, size - 1, st, ed, e); }
SegmentTree { public void updateRange(int st, int ed, E e) { if (extraUpdater == null || extraMerger == null) throw new IllegalStateException("extraUpdater OR extraMerger should not be null in range update"); if (st < 0 || ed >= size || st > ed) throw new IllegalArgumentException("invalid range"); updateRange(0, 0, size - 1, st, ed, e); } }
SegmentTree { public void updateRange(int st, int ed, E e) { if (extraUpdater == null || extraMerger == null) throw new IllegalStateException("extraUpdater OR extraMerger should not be null in range update"); if (st < 0 || ed >= size || st > ed) throw new IllegalArgumentException("invalid range"); updateRange(0, 0, size - 1, st, ed, e); } SegmentTree(E[] data, Merger<E> function, Merger<E> extraMerger, Updater<E> extraUpdater); }
SegmentTree { public void updateRange(int st, int ed, E e) { if (extraUpdater == null || extraMerger == null) throw new IllegalStateException("extraUpdater OR extraMerger should not be null in range update"); if (st < 0 || ed >= size || st > ed) throw new IllegalArgumentException("invalid range"); updateRange(0, 0, size - 1, st, ed, e); } SegmentTree(E[] data, Merger<E> function, Merger<E> extraMerger, Updater<E> extraUpdater); E query(int st, int ed); void set(int idx, E e); void updateRange(int st, int ed, E e); @Override String toString(); }
SegmentTree { public void updateRange(int st, int ed, E e) { if (extraUpdater == null || extraMerger == null) throw new IllegalStateException("extraUpdater OR extraMerger should not be null in range update"); if (st < 0 || ed >= size || st > ed) throw new IllegalArgumentException("invalid range"); updateRange(0, 0, size - 1, st, ed, e); } SegmentTree(E[] data, Merger<E> function, Merger<E> extraMerger, Updater<E> extraUpdater); E query(int st, int ed); void set(int idx, E e); void updateRange(int st, int ed, E e); @Override String toString();  }