### 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.

**Programming language**: Swift

**License**: MIT License

**Latest version**: v0.0.7

# 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.
*