{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T21:03:17Z","timestamp":1760043797457,"version":"3.33.0"},"reference-count":13,"publisher":"Cambridge University Press (CUP)","license":[{"start":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T00:00:00Z","timestamp":1737072000000},"content-version":"unspecified","delay-in-days":16,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[2025]]},"abstract":"<jats:title>Abstract<\/jats:title>\n\t  <jats:p><jats:italic>Fenwick trees<\/jats:italic>, also known as <jats:italic>binary indexed trees<\/jats:italic> are a clever solution to the problem of maintaining a sequence of values while allowing both updates and range queries in sublinear time. Their implementation is concise and efficient\u2014but also somewhat baffling, consisting largely of nonobvious bitwise operations on indices. We begin with <jats:italic>segment trees<\/jats:italic>, a much more straightforward, easy-to-verify, purely functional solution to the problem, and use equational reasoning to explain the implementation of Fenwick trees as an optimized variant, making use of a Haskell EDSL for operations on infinite two\u2019s complement binary numbers.<\/jats:p>","DOI":"10.1017\/s0956796824000169","type":"journal-article","created":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T08:43:22Z","timestamp":1737103402000},"update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["You could have invented Fenwick trees"],"prefix":"10.1017","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-0135-6134","authenticated-orcid":false,"given":"BRENT","family":"YORGEY","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2025,1,17]]},"reference":[{"key":"S0956796824000169_ref10","doi-asserted-by":"publisher","DOI":"10.1145\/2976002.2976013"},{"key":"S0956796824000169_ref8","unstructured":"Ivanov, M. (2011a) Fenwick tree. https:\/\/cp-algorithms.com\/data_structures\/fenwick.html. [Online; accessed 21-Nov-2024]."},{"key":"S0956796824000169_ref11","doi-asserted-by":"publisher","DOI":"10.1147\/rd.232.0149"},{"key":"S0956796824000169_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380240306"},{"key":"S0956796824000169_ref12","first-page":"548","volume-title":"Doklady Akademii Nauk","author":"Ryabko","year":"1989"},{"key":"S0956796824000169_ref13","unstructured":"Wikipedia Contributors. (2024) Segment tree \u2014 Wikipedia, the free encyclopedia. https:\/\/en.wikipedia.org\/wiki\/Segment_tree. [Online; accessed 03-Jun-2024]."},{"key":"S0956796824000169_ref9","unstructured":"Ivanov, M. (2011b) Segment tree. https:\/\/cp-algorithms.com\/data_structures\/segment_tree.html. [Online; accessed 03-Jun-2024]."},{"key":"S0956796824000169_ref1","unstructured":"Apfelmus, H. (2009) Monoids and finger trees. https:\/\/apfelmus.nfshost.com\/articles\/monoid-fingertree.html. [Online; accessed 10-Jun-2024]."},{"key":"S0956796824000169_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(05)80540-7"},{"key":"S0956796824000169_ref3","doi-asserted-by":"publisher","DOI":"10.1145\/351240.351266"},{"key":"S0956796824000169_ref2","doi-asserted-by":"crossref","unstructured":"Bird, R. & Gibbons, J. (2002) Arithmetic coding with folds and unfolds. In International School on Advanced Functional Programming. Springer, pp. 1\u201326.","DOI":"10.1007\/978-3-540-44833-4_1"},{"key":"S0956796824000169_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796805005769"},{"key":"S0956796824000169_ref6","volume-title":"Competitive Programming 4: The Lower Bound of Programming Contests in the 2020s","author":"Halim","year":"2020"}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796824000169","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T08:43:27Z","timestamp":1737103407000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796824000169\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"references-count":13,"alternative-id":["S0956796824000169"],"URL":"https:\/\/doi.org\/10.1017\/s0956796824000169","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}],"article-number":"e3"}}