#Segment-Tree

2 posts

Matrix #1 April 28, 2026 17 min read

Matrix Fast Power — Linear Recurrence, DP Semirings & Kitamasa

Matrix fast power for linear recurrences (4 patterns), 4 semiring templates (count/bool/min-plus/max-plus), matrix+segment tree for range-add Fibonacci queries, Kitamasa O(k²logn) and NTT O(k log²k logn).

#math #matrix #fast-power #linear-recurrence #dp

Matrix #4 April 28, 2026 6 min read

Matrix Problems — Fibonacci Subarray Sums, Gaussian Elimination & Expected Value

Hard matrix problems: Fibonacci squared subarray sum with segment-tree 4-tuple and companion matrix; cycle-decomposition partition state space for random-swap sorting, first-step analysis, and Gaussian elimination.

#math #matrix #segment-tree #gaussian-elimination #expected-value