Segment Tree in Java

Segment Tree

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

// Create an initial tree with an array, and a binary operator.
// The binary operator can be adder, multiplier or anything you define.

Array<Integer> init = MutableArrayFromVarargs.create(4, 3, 1, 5, 2);

SegmentTree<Integer> maxTree = GoodSegmentTreeFactory.getInstance().create(init, new BinaryOperator<Integer>() {
	@Override
	public Integer calc(Integer a, Integer b) {
		return Math.max(a, b);
	}
});

// query by range.

int max1 = maxTree.query(1, 4); // maximum is 5 among (3, 1, 5)

// update one element. and query again to get updated result.

maxTree.update(2, 99);

int max2 = maxTree.query(1, 4); // now, maximum is 99 among (3, 99, 5)

Implementation

SegmentTreeByArrayImplementation.java in GitHub