Description
Dynamically stores additive values and get arbitrary sub-range sums in O(log(n)) time.
This is an implementation of something called "segment-tree" or "interval-tree".
You insert/remove lengths of consecutive segments and query positions on it.
I'm not sure which one is correct name.
SegmentQuery alternatives and similar libraries
Based on the "Algorithm" category.
Alternatively, view SegmentQuery alternatives based on common mentions on social networks and blogs.
* Code Quality Rankings and insights are calculated and provided by Lumnify.
They vary from L1 to L5 with "L5" being the highest.
Do you think we are missing an alternative of SegmentQuery or a related project?
README
SegmentQuery
Eonil, 2019.
Dynamically stores additive values and get arbitrary sub-range sums in O(log(n)) time.
This is an implementation of something called "segment-tree" or "interval-tree". You insert/remove lengths of consecutive segments and query positions on it. I'm not sure which one is correct name.
How to Use
Add dependency.
.package(url: "https://github.com/eonil/swift-segment-query", .branch("master")),
And use.
import SegmentQuery
var x = SegmentQuery<Int>()
/// Append segment lengths.
x.append(contentsOf: [111,222,333])
/// Get subrange sum.
let s = x[1..<3].sum
assert(s == 222+333)
/// Get start/end offsets of a segment 1.
let a = x[..<1].sum
let b = x[...1].sum
let c = a..<b
/// Get index of segment and in-segment-offset from an offset.
let (a,b) = x.location(at: 230)
assert(a == 1)
assert(b == 8)
Requirements
- Swift 5.x.
- Swift Package Manager.
Complexity
- O(log(n)) for element query/insert/update/remove and sub-sum query.
Performance
I couldn't find other segment query library written in Swift for comparison.
Instead, I performed insert/remove performance comparison
with well-known B-Tree library written by Lőrentey.
This is one-by-one random Int number insert/remove at random location on 64-bit macOS,
With list of 128K values,
- 4x faster than
Swift.Array. - Very close speed to
BTree.List.
With list of 1 million values,
- 4x faster than
BTree.List.
Run SegmentQueryBenchmark to get numbers on your machine.
Implementation
- B-Tree based with no key stored.
- Only values are stored.
- Values are stored only on leafs.
- Buffer sizes are optimized for ordered list behavior with dynamic automatic sum.
Missing Features
- Balancing after remove. (Now only insertion is balanced by B-Tree insertion algorithm)
- Bulk insert/remove implementation.
- Sequential element iteration in O(n) time. Now it's O(n log n).
- Sub-sum indexing in each node. We can store sub-sum for each branch/leaf node children to perform binary search to get an item. There is a trade-off, but I didn't try due to lack of time.
Credit & License
Copyright(C) Eonil 2019. All rights reserved. Using of this code is licensed under "MIT License".
*Note that all licence references and agreements mentioned in the SegmentQuery README section above
are relevant to that project's source code only.