Segment Tree With Lazy Propagation in Java

Segment Tree With Lazy Propagation

Download

Download jar file or use maven. psjava requires Java 1.6 (or above)

<dependency>
    <groupId>org.psjava</groupId>
    <artifactId>psjava</artifactId>
    <version>0.1.19</version>
</dependency>

Example Code

// This is an advanced version of segment tree.
// This updates the values of given range in O(logn) time.

Array<Integer> init = MutableArrayFromVarargs.create(1, 1, 1, 1, 1);

RangeUpdatableSegmentTree<Integer> sumTree = RangeUpdatableSegmentTree.create(init, new BinaryOperator<Integer>() {
	@Override
	public Integer calc(Integer a, Integer b) {
		return a + b;
	}
});

// Query by range.

int sum1 = sumTree.query(0, 5); // must be 5=1+1+1+1+1

// Update by range, this is done fast!

sumTree.updateRange(1, 4, 100);
int sum2 = sumTree.query(0, 5); // must be 302=1+100+100+100+1

Implementation

LazyPropagatingSegmentTree.java in GitHub
RangeUpdatableSegmentTree.java in GitHub