{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T14:15:35Z","timestamp":1775830535406,"version":"3.50.1"},"reference-count":5,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,30]],"date-time":"2006-10-30T00:00:00Z","timestamp":1162166400000},"content-version":"vor","delay-in-days":4626,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Softw Pract Exp"],"published-print":{"date-parts":[[1994,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A new method (the \u2018binary indexed tree\u2019) is presented for maintaining the cumulative frequencies which are needed to support dynamic arithmetic data compression. It is based on a decomposition of the cumulative frequencies into portions which parallel the binary representation of the index of the table element (or symbol). The operations to traverse the data structure are based on the binary coding of the index. In comparison with previous methods, the binary indexed tree is faster, using more compact data and simpler code. The access time for all operations is either constant or proportional to the logarithm of the table size. In conjunction with the compact data structure, this makes the new method particularly suitable for large symbol alphabets.<\/jats:p>","DOI":"10.1002\/spe.4380240306","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T16:56:38Z","timestamp":1163782598000},"page":"327-336","source":"Crossref","is-referenced-by-count":128,"title":["A new data structure for cumulative frequency tables"],"prefix":"10.1002","volume":"24","author":[{"given":"Peter M.","family":"Fenwick","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,30]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/214762.214771"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.52489"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/63030.63036"},{"key":"e_1_2_1_5_2","unstructured":"P. C.Gutmann \u2018Practical dictionary\/arithmetic data compression synthesis\u2019 MSc Thesis University of Auckland February1992."},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380190207"}],"container-title":["Software: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fspe.4380240306","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.4380240306","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T13:28:51Z","timestamp":1698154131000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/spe.4380240306"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,3]]},"references-count":5,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,3]]}},"alternative-id":["10.1002\/spe.4380240306"],"URL":"https:\/\/doi.org\/10.1002\/spe.4380240306","archive":["Portico"],"relation":{},"ISSN":["0038-0644","1097-024X"],"issn-type":[{"value":"0038-0644","type":"print"},{"value":"1097-024X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,3]]}}}