ordered-collections.types.segment-tree — com.dean/ordered-collections 0.2.0

A segment tree for efficient range aggregate queries.

Supports O(log n) point updates and O(log n) range queries for any associative operation (sum, min, max, gcd, etc.).

CONCEPT: Each node stores an aggregate of its entire subtree. For sum:

             ┌─────────────┐
             │ key: 3      │
             │ val: 40     │
             │ agg: 150 ◄──────── sum of entire tree
             └──────┬──────┘
        ┌───────────┴───────────┐
 ┌──────┴──────┐         ┌──────┴──────┐
 │ key: 1      │         │ key: 4      │
 │ val: 20     │         │ val: 50     │
 │ agg: 30 ◄───────      │ agg: 80 ◄───────
 └──────┬──────┘   │     └──────┬──────┘   │
        │          │            │          │
 ┌──────┴──────┐   │     ┌──────┴──────┐   │
 │ key: 0      │   │     │ key: 5      │   │
 │ val: 10     │   │     │ val: 30     │   │
 │ agg: 10     │   │     │ agg: 30     │   │
 └─────────────┘   │     └─────────────┘   │
                   │                       │
        10 + 20 = 30              50 + 30 = 80

RANGE QUERY: query(1, 4) = sum of indices 1,2,3,4 Uses aggregates to avoid visiting every node - O(log n).

EXAMPLE: (def st (segment-tree + 0 {0 10, 1 20, 2 30, 3 40, 4 50})) (query st 0 4) ; => 150 (sum of all) (query st 1 3) ; => 90 (20 + 30 + 40) (update st 2 100) ; => new tree with index 2 = 100 (query st 1 3) ; => 160 (20 + 100 + 40)

max-tree clj

(max-tree coll)

Create a segment tree for range maximum queries. (query st lo hi) returns maximum value in [lo, hi].

min-tree clj

(min-tree coll)

Create a segment tree for range minimum queries. (query st lo hi) returns minimum value in [lo, hi].

segment-tree clj

(segment-tree op identity)

(segment-tree op identity coll)

Create a segment tree with the given associative operation and identity.

Arguments: op - associative binary operation (e.g., +, min, max) identity - identity element for op (e.g., 0 for +, Long/MAX_VALUE for min) coll - map or seq of [key value] pairs

Example: ;; Sum segment tree (segment-tree + 0 {0 10, 1 20, 2 30})

;; Min segment tree (segment-tree min Long/MAX_VALUE {0 5, 1 3, 2 8})

;; Max segment tree (segment-tree max Long/MIN_VALUE [[0 5] [1 3] [2 8]])

segment-tree-by clj

(segment-tree-by pred op identity coll)

Create a segment tree with a custom ordering predicate.

The predicate should define a total order like < or >.

segment-tree-with clj

(segment-tree-with comparator op identity)

(segment-tree-with comparator op identity coll)

Create a segment tree with a custom comparator.

The comparator controls key ordering for point lookups, updates, and range queries.

sum-tree clj

(sum-tree coll)

Create a segment tree for range sums. (query st lo hi) returns sum of values in [lo, hi].