Skip to content

Instantly share code, notes, and snippets.

@sushain97
Last active December 9, 2021 17:24
Show Gist options
  • Save sushain97/ca1aeb8930f5c44d376ada3b38b5c42f to your computer and use it in GitHub Desktop.
Save sushain97/ca1aeb8930f5c44d376ada3b38b5c42f to your computer and use it in GitHub Desktop.
Fenwick tree implemented in J
NB. Implementation TODO: customizing assoc. fn?, custom OOB error?
coclass 'FenwickTree'
lsb =. #.@(#:*.#:@-) NB. TODO: Can I get rid of the repeated #.?
add =: 4 : 0 NB. i add v
idxs =. }:(<.&(#arr))@(+lsb@>:)^:a:x
arr =: (y+idxs{arr)idxs}arr
)
create =: 3 : 'arr =: y $ 0' NB. N TODO: Can this be tacit?
range =: 3 : 0 NB. range i j TODO: Can I accept only #2 list?
'i j' =. y
js =. (>.&i)@(-lsb)^:a:j
j =. (-lsb)^:(<:#js)j
(+/(<:}:js){arr)-(+/(<:}:(>.&j)@(-lsb)^:a:i){arr)
)
get =: range@(,>:) NB. get i TODO: Can I make this "0 permanently?
set =: [add]-(get@[) NB. i set v
NB. implement init?
NB. Tests
cocurrent 'base'
T =. 10 conew 'FenwickTree'
shouldbe =. 3 : 'assert (get__T"0(i.10)) = y' NB. TODO: Can this be tacit?
assert (get__T"0(i.10)) = 0 0 0 0 0 0 0 0 0 0
3 set__T 5
assert (get__T"0(i.10)) = 0 0 0 5 0 0 0 0 0 0
3 set__T 8
assert (get__T"0(i.10)) = 0 0 0 8 0 0 0 0 0 0
8 set__T 3
assert (get__T"0(i.10)) = 0 0 0 8 0 0 0 0 3 0
0 set__T 2
assert (get__T"0(i.10)) = 2 0 0 8 0 0 0 0 3 0
assert (range__T 0 9) = (+/ 2 0 0 8 0 0 0 0 3 0)
assert (range__T 0 2) = (+/ 3 {. 2 0 0 8 0 0 0 0 3 0)
assert (range__T 7 9) = (+/ _3 {. 2 0 0 8 0 0 0 0 3 0)
assert (range__T 3 7) = 8
5 set__T 7
assert (get__T"0(i.10)) = 2 0 0 8 0 7 0 0 3 0
assert (range__T 3 7) = 15
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment