code wiki / (root) / nx_sketch_segment_tree.nx

nx_sketch_segment_tree.nx

buildroot/runtime/nx_sketch_segment_tree.nx

6137 B210 linesdepth 3pulls 3 transitivereach 0 importersview sourcekind sketch/demotopic sketch
docsdependenciesstructsconstsfunctions

about

sketch_segment_tree.nx -- segment tree for range sum / min / max queries. Foundational data structure. Array of N elements, supports: point_update(i, value) O(log N) range_sum(lo, hi) O(log N) range_min(lo, hi) O(log N) range_max(lo, hi) O(log N) All three aggregates are maintained per node so callers don't have to pick a single aggregate at construction. Memory: 3 * 2N i64s (sum/min/max per node) for N-element backing array. USE CASES: - online range-sum queries (stocks-OHLC over time-window) - dynamic-programming acceleration (e.g., longest increasing subseq) - inverse-index aggregation - online statistics over sliding indexed ranges API uses HALF-OPEN intervals: range_*(lo, hi) covers indices [lo, hi). LOSSLESS-LANGUAGE DISCIPLINE: all queries EXACT. Production tier. Initialized to: sum = 0 min = +MAX (so unwritten slots don't affect min) max = -MAX (similar) Caller responsibility: point_update before query for meaningful min/max over ranges containing unwritten slots.

dependencies 2 imports · 0 importers

nx_syscalls.nx nx_sketch_types.nx nx_sketch_segment_tree.nx

imports: nx_syscalls.nxnx_sketch_types.nx

imported by: nobody (leaf or entry point)

structs

44struct SegmentTree

consts

38const NX_ST_MIN_N: i64 = 2
39const NX_ST_MAX_N: i64 = 1000000
41const NX_ST_PLUS_INF: i64 = 0x4000000000000000
42const NX_ST_MINUS_INF: i64 = -0x4000000000000000

functions

54func nx_st_next_pow2(n: i64) -> i64
called by 1: nx_st_alloc
60func nx_st_alloc(n: i64) -> *SegmentTree
calls 2: sys_mmapnx_st_next_pow2
84func nx_st_min2(a: i64, b: i64) -> i64
called by 2: nx_st_updatenx_st_range_min
89func nx_st_max2(a: i64, b: i64) -> i64
called by 2: nx_st_updatenx_st_range_max
98func nx_st_update(t: *SegmentTree, idx: i64, value: i64) -> i64
calls 2: nx_st_min2nx_st_max2
123func nx_st_range_sum(t: *SegmentTree, lo: i64, hi: i64) -> i64
called by 1: nx_st_query_sum
145func nx_st_range_min(t: *SegmentTree, lo: i64, hi: i64) -> i64
calls 1: nx_st_min2
167func nx_st_range_max(t: *SegmentTree, lo: i64, hi: i64) -> i64
calls 1: nx_st_max2
191func nx_st_get(t: *SegmentTree, idx: i64) -> i64
199func nx_st_query_sum(t: *SegmentTree, lo: i64, hi: i64) -> *ApproxI64
calls 2: nx_st_range_sumnx_approx_new
206func nx_st_memory_bytes(t: *SegmentTree) -> i64
210func nx_st_n(t: *SegmentTree) -> i64 { return t.n }