code wiki / (root) / sketch_segment_tree.nx

sketch_segment_tree.nx

buildroot/runtime/sketch_segment_tree.nx

6084 B204 linesdepth 4pulls 4 transitivereach 1 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 · 1 importers

syscalls.nx sketch_types.nx sketch_segment_tree.nx sketch_segment_tree_test.nx

imports: syscalls.nxsketch_types.nx

imported by: sketch_segment_tree_test.nx

structs

38struct SegmentTree {

consts

32const NX_ST_MIN_N: i64 = 2
33const NX_ST_MAX_N: i64 = 1000000
35const NX_ST_PLUS_INF: i64 = 0x4000000000000000
36const NX_ST_MINUS_INF: i64 = -0x4000000000000000

functions

48func nx_st_next_pow2(n: i64) -> i64 {
called by 1: nx_st_alloc
54func nx_st_alloc(n: i64) -> *SegmentTree {
called by 1: main calls 1: nx_st_next_pow2
78func nx_st_min2(a: i64, b: i64) -> i64 {
called by 2: nx_st_updatenx_st_range_min
83func nx_st_max2(a: i64, b: i64) -> i64 {
called by 2: nx_st_updatenx_st_range_max
92func nx_st_update(t: *SegmentTree, idx: i64, value: i64) -> i64 {
called by 1: main calls 2: nx_st_min2nx_st_max2
117func nx_st_range_sum(t: *SegmentTree, lo: i64, hi: i64) -> i64 {
called by 2: nx_st_query_summain
139func nx_st_range_min(t: *SegmentTree, lo: i64, hi: i64) -> i64 {
called by 1: main calls 1: nx_st_min2
161func nx_st_range_max(t: *SegmentTree, lo: i64, hi: i64) -> i64 {
called by 1: main calls 1: nx_st_max2
185func nx_st_get(t: *SegmentTree, idx: i64) -> i64 {
called by 1: main
193func nx_st_query_sum(t: *SegmentTree, lo: i64, hi: i64) -> *ApproxI64 {
called by 1: main calls 2: nx_st_range_sumnx_approx_new
200func nx_st_memory_bytes(t: *SegmentTree) -> i64 {
204func nx_st_n(t: *SegmentTree) -> i64 { return t.n }