nx_sketch_segment_tree.nx source
↩ module page · 210 lines · 6137 B
1// sketch_segment_tree.nx -- segment tree for range sum / min / max queries.
2//
3// Foundational data structure. Array of N elements, supports:
4// point_update(i, value) O(log N)
5// range_sum(lo, hi) O(log N)
6// range_min(lo, hi) O(log N)
7// range_max(lo, hi) O(log N)
8//
9// All three aggregates are maintained per node so callers don't have to
10// pick a single aggregate at construction. Memory: 3 * 2N i64s
11// (sum/min/max per node) for N-element backing array.
12//
13// USE CASES:
14// - online range-sum queries (stocks-OHLC over time-window)
15// - dynamic-programming acceleration (e.g., longest increasing subseq)
16// - inverse-index aggregation
17// - online statistics over sliding indexed ranges
18//
19// API uses HALF-OPEN intervals: range_*(lo, hi) covers indices [lo, hi).
20//
21// LOSSLESS-LANGUAGE DISCIPLINE: all queries EXACT. Production tier.
22// Initialized to:
23// sum = 0
24// min = +MAX (so unwritten slots don't affect min)
25// max = -MAX (similar)
26// Caller responsibility: point_update before query for meaningful min/max
27// over ranges containing unwritten slots.
28
29// nx_safety_envelope:
30// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
31// sil_target: SIL1
32// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
33// verdict: NOT_YET_EVALUATED
34
35import "nx_syscalls.nx"
36import "nx_sketch_types.nx"
37
38const NX_ST_MIN_N: i64 = 2
39const NX_ST_MAX_N: i64 = 1000000
40
41const NX_ST_PLUS_INF: i64 = 0x4000000000000000
42const NX_ST_MINUS_INF: i64 = -0x4000000000000000
43
44struct SegmentTree {
45 n: i64,
46 capacity: i64, // next power of 2 >= n
47 sum: *i64, // 2 * capacity entries; index 1 is root
48 min_arr: *i64,
49 max_arr: *i64,
50}
51
52// === construction =================================================
53
54func nx_st_next_pow2(n: i64) -> i64 {
55 var p: i64 = 1
56 while p < n { p = p << 1 }
57 return p
58}
59
60func nx_st_alloc(n: i64) -> *SegmentTree {
61 if n < NX_ST_MIN_N { return 0 as *SegmentTree }
62 if n > NX_ST_MAX_N { return 0 as *SegmentTree }
63 let raw: *u8 = sys_mmap(56)
64 let t: *SegmentTree = raw as *SegmentTree
65 let cap: i64 = nx_st_next_pow2(n)
66 let cells: i64 = 2 * cap
67 t.sum = sys_mmap(cells * 8) as *i64
68 t.min_arr = sys_mmap(cells * 8) as *i64
69 t.max_arr = sys_mmap(cells * 8) as *i64
70 var i: i64 = 0
71 while i < cells {
72 t.sum[i] = 0
73 t.min_arr[i] = NX_ST_PLUS_INF
74 t.max_arr[i] = NX_ST_MINUS_INF
75 i = i + 1
76 }
77 t.n = n
78 t.capacity = cap
79 return t
80}
81
82// === min/max helpers ==============================================
83
84func nx_st_min2(a: i64, b: i64) -> i64 {
85 if a < b { return a }
86 return b
87}
88
89func nx_st_max2(a: i64, b: i64) -> i64 {
90 if a > b { return a }
91 return b
92}
93
94// === point update ================================================
95//
96// Set value at leaf index `idx` to `value`; propagate up to root.
97
98func nx_st_update(t: *SegmentTree, idx: i64, value: i64) -> i64 {
99 if idx < 0 { return -1 }
100 if idx >= t.n { return -1 }
101 // Leaves stored at positions capacity..2*capacity-1.
102 var pos: i64 = t.capacity + idx
103 t.sum[pos] = value
104 t.min_arr[pos] = value
105 t.max_arr[pos] = value
106 pos = pos >> 1
107 while pos > 0 {
108 let lc: i64 = 2 * pos
109 let rc: i64 = 2 * pos + 1
110 t.sum[pos] = t.sum[lc] + t.sum[rc]
111 t.min_arr[pos] = nx_st_min2(t.min_arr[lc], t.min_arr[rc])
112 t.max_arr[pos] = nx_st_max2(t.max_arr[lc], t.max_arr[rc])
113 pos = pos >> 1
114 }
115 return 0
116}
117
118// === range query helpers ==========================================
119//
120// Iterative range queries over [lo, hi) in leaf indices.
121// Translates to leaf positions [capacity+lo, capacity+hi).
122
123func nx_st_range_sum(t: *SegmentTree, lo: i64, hi: i64) -> i64 {
124 if lo < 0 { return 0 }
125 if hi > t.n { return 0 }
126 if lo >= hi { return 0 }
127 var l: i64 = t.capacity + lo
128 var r: i64 = t.capacity + hi
129 var acc: i64 = 0
130 while l < r {
131 if (l & 1) == 1 {
132 acc = acc + t.sum[l]
133 l = l + 1
134 }
135 if (r & 1) == 1 {
136 r = r - 1
137 acc = acc + t.sum[r]
138 }
139 l = l >> 1
140 r = r >> 1
141 }
142 return acc
143}
144
145func nx_st_range_min(t: *SegmentTree, lo: i64, hi: i64) -> i64 {
146 if lo < 0 { return NX_ST_PLUS_INF }
147 if hi > t.n { return NX_ST_PLUS_INF }
148 if lo >= hi { return NX_ST_PLUS_INF }
149 var l: i64 = t.capacity + lo
150 var r: i64 = t.capacity + hi
151 var acc: i64 = NX_ST_PLUS_INF
152 while l < r {
153 if (l & 1) == 1 {
154 acc = nx_st_min2(acc, t.min_arr[l])
155 l = l + 1
156 }
157 if (r & 1) == 1 {
158 r = r - 1
159 acc = nx_st_min2(acc, t.min_arr[r])
160 }
161 l = l >> 1
162 r = r >> 1
163 }
164 return acc
165}
166
167func nx_st_range_max(t: *SegmentTree, lo: i64, hi: i64) -> i64 {
168 if lo < 0 { return NX_ST_MINUS_INF }
169 if hi > t.n { return NX_ST_MINUS_INF }
170 if lo >= hi { return NX_ST_MINUS_INF }
171 var l: i64 = t.capacity + lo
172 var r: i64 = t.capacity + hi
173 var acc: i64 = NX_ST_MINUS_INF
174 while l < r {
175 if (l & 1) == 1 {
176 acc = nx_st_max2(acc, t.max_arr[l])
177 l = l + 1
178 }
179 if (r & 1) == 1 {
180 r = r - 1
181 acc = nx_st_max2(acc, t.max_arr[r])
182 }
183 l = l >> 1
184 r = r >> 1
185 }
186 return acc
187}
188
189// === point read ==================================================
190
191func nx_st_get(t: *SegmentTree, idx: i64) -> i64 {
192 if idx < 0 { return 0 }
193 if idx >= t.n { return 0 }
194 return t.sum[t.capacity + idx]
195}
196
197// === typed query =================================================
198
199func nx_st_query_sum(t: *SegmentTree, lo: i64, hi: i64) -> *ApproxI64 {
200 let s: i64 = nx_st_range_sum(t, lo, hi)
201 return nx_approx_new(s, NX_ENV_ABS, 0, 1000000000,
202 NX_MATURITY_PRODUCTION,
203 NX_ADV_HONEST)
204}
205
206func nx_st_memory_bytes(t: *SegmentTree) -> i64 {
207 return 56 + 3 * 2 * t.capacity * 8
208}
209
210func nx_st_n(t: *SegmentTree) -> i64 { return t.n }