Package Struct
Class SegTree<T,R>
java.lang.Object
Struct.SegTree<T,R>
- Type Parameters:
T
- The type of the input elements stored in the initial array.R
- The result or operation type after applying the map and accumulation functions.
A generic segment tree implementation that provides efficient range query and point update operations.
The tree allows aggregation of results over a segment of an array and is built based on provided mapping and accumulation functions.
- Since:
- 1.0
- Version:
- 1.0
- Author:
- Sahasrad Chippa
-
Constructor Summary
Constructors -
Method Summary
-
Constructor Details
-
SegTree
Constructs a segment tree from an array. Runs inO(n)
.- Parameters:
arr
- An array of type T from which the segment tree will be built.individualMapper
- A function to convert array elements of type T to the segment type R.accumulator
- A function to accumulate two segments of type R.
-
SegTree
Constructs a segment tree from a list. Runs inO(n)
.- Parameters:
list
- A list of type T from which the segment tree will be built.individualMapper
- A function to convert list elements of type T to the segment type R.accumulator
- A function to accumulate two segments of type R.
-
-
Method Details
-
query
Queries the aggregate value over a range [l, r]. Runs inO(log(n))
.- Parameters:
l
- The left index of the range.r
- The right index of the range.- Returns:
- The aggregated result over the range.
- Throws:
IllegalArgumentException
- If indexesl
andr
are not a valid range (where0 <= l <= r < n
).
-
set
Updates the value at a specific index. Runs inO(log(n))
.- Parameters:
index
- The index to update.val
- The new value of type T.
-