1662:
78:
25:
2519:
The search tree may be considered a combination of the previous two trees. A node's left subtree contains all of its descendants in the update tree, while its right subtree contains all of its descendants in the interrogation tree. A node's parent in the search tree is either its interrogation or
264:
values can either store the values or the prefix sums. In the first case, computing prefix sums requires linear time; in the second case, updating the array values requires linear time (in both cases, the other operation can be performed in constant time). Fenwick trees allow both operations to be
2527:
traversal through the search tree. During the traversal, three variables are maintained: The current node's index, the rank being sought in the subtree rooted at the current node, and a "fallback index" to be returned if the rank sought is greater than can be found in the subtree.
2264:
calls a "sideways heap". Each node is assigned a height equal to the number of trailing zeros in the binary representation of its index, with the parent and children being the numerically closest index(es) of the adjacent height. Nodes with odd indexes
411:(addition on integers being by far the most common). Fenwick trees provide a method to query the running total at any index, or prefix sum, in addition to allowing changes to the underlying value array and having all further queries reflect those changes.
2445:
240:
This structure was proposed by Boris Ryabko in 1989 with a further modification published in 1992. It has subsequently become known under the name
Fenwick tree after Peter Fenwick, who described this structure in his 1994 article.
2633:
for the current node, we must search its left subtree. If it is greater, search its right subtree. If it is equal, the direction chosen depends on how you wish to handle searches for sums lying exactly between two nodes.
330:
nodes where the value of each node in the tree is the prefix sum of the array from the index of the parent (inclusive) up to the index of the node (exclusive). The tree itself is implicit and can be stored as an array of
1100:
1939:
811:
2912:
1434:
520:
1601:
1507:
916:
2347:
351:
values, with the implicit root node omitted from the array. The tree structure allows the operations of value retrieval, value update, prefix sum, and range sum to be performed using only
1286:
2301:
666:
1633:
843:
2845:
2753:
2523:
However, upward traversals in the search tree are uncommon; its primary use is to perform rank queries: given a prefix sum, at what index does it appear? This is done by a
2520:
update parent (depending on whether the node is a right or left child, respectively), and the other type of parent may be found by multiple upward steps in the search tree.
244:
When compared with a flat array of values, the
Fenwick tree achieves a much better balance between two operations: value update and prefix sum calculation. A flat array of
2972:
1787:
1717:
989:
384:
298:
2516:
yet still have an existing grandparent. If the example above applied to a 5-node tree, then node 5 would have a fictitious parent 6, but an existing grandparent 4.
2145:
2081:
3001:
2579:
1813:
1312:
1203:
1177:
328:
2934:
One naive algorithm to construct a
Fenwick tree consists of initializing the tree with null values and updating each index individually. This solution works in
2808:
2784:
2631:
2602:
2553:
2514:
2491:
2367:
2246:
2226:
2206:
2177:
2110:
2046:
2014:
1994:
1974:
1861:
1833:
1737:
1653:
1456:
1151:
1131:
1036:
945:
872:
735:
706:
686:
579:
559:
467:
349:
262:
2372:
2604:), or we must decide if the position sought is to the left or right of the end of the current node. If the rank sought is less than the Fenwick array value
2669:
the target is in its right subtree, search for the target rank minus the current node's value in the right subtree, with an unchanged fallback index.
1658:
The below diagram shows the structure of a 16-node
Fenwick tree's interrogation tree, including the root, so it corresponds to a 15-element array A:
46:
33:
1010:
for translating prefix sums to indexes (rank queries). The first two are normally walked upwards, while the third is usually walked downwards.
3571:
3778:
1041:
1866:
3322:
743:
3261:
2850:
1317:
476:
3834:
1512:
3438:
3280:
3238:
3290:
2666:
the target is in its left subtree, search for the same rank in its left subtree with the current index as the fallback index.
738:
422:
of a symbol less than a given symbol. Development of operations it supports were primarily motivated by use in that case.
469:. This is the power of two (1, 2, 4, 8, ...) and not the exponent (0, 1, 2, 3, ...). It can be efficiently computed in
434:
where nodes are consecutively numbered, and parent-child relationships are determined by arithmetic on the node indexes.
1461:
3844:
880:
877:
A fictitious node 0 is used in some descriptions, but is never actually accessed and need not be explicitly stored.
3132:
2306:
3839:
3403:
38:
3788:
3092:
1208:
3344:
2268:
588:
1606:
816:
2531:
Initially, the current node is the root, the rank sought is the original query, and the fallback index is a
431:
85:
3315:
3168:
419:
1739:, its parent, its parent's parent, and so on up to (but not including) the root. To compute a range sum
3482:
3331:
2813:
2303:) are leaves. Nodes with even indexes have the closest two nodes of the next-lowest index as children,
301:
2637:
These three possibilities are then further divided based on whether the current node is a leaf or not:
3472:
3427:
3046:
2727:
405:
3586:
3362:
3173:
470:
3442:
2937:
3753:
3712:
3538:
3528:
3407:
3209:
3186:
1742:
1672:
950:
582:
530:
2663:
it is fictitious, search for the same rank in its left subtree with an unchanged fallback index.
354:
268:
3647:
3348:
3308:
3257:
2684:
implementation of the two main operations on a
Fenwick tree—query and update—is as following:
415:
3738:
3205:
3178:
2115:
2051:
1996:
it will be a forest of disjoint trees, one for each bit set in the binary representation of
1665:
Depiction of a 16-node
Fenwick interrogation tree containing range sums of a 15-node array A
418:
algorithm, which maintains counts of each symbol produced and needs to convert those to the
408:
187:
3682:
3432:
2977:
115:
2558:
1792:
1291:
1182:
1156:
307:
2440:{\displaystyle (i-\operatorname {lsb} (i))\mathbin {|} (2\cdot \operatorname {lsb} (i))}
3635:
3630:
3513:
3447:
2923:
2793:
2769:
2607:
2587:
2538:
2532:
2499:
2476:
2352:
2231:
2211:
2182:
2153:
2086:
2022:
2019:
Here, a node's ancestors are all nodes whose range sums include its own. For example,
1999:
1979:
1959:
1846:
1818:
1722:
1638:
1441:
1136:
1116:
1021:
921:
848:
711:
691:
671:
564:
535:
452:
442:
334:
247:
119:
3241:. Vol. 4A. Upper Saddle River, NJ: Addison-Wesley Professional. pp. 164–165.
3828:
3783:
3763:
3606:
3495:
3422:
3285:
2757:
2469:
Although this tree is potentially infinite, we may define its root to be the highest
401:
3357:
1661:
77:
3707:
3523:
3518:
3500:
3412:
3230:
3190:
3056:
2787:
2261:
1843:
The update tree is the mirror image of the interrogation tree. The parent of node
446:
3159:
Peter M. Fenwick (1994). "A new data structure for cumulative frequency tables".
2496:
It is possible for a node to have a fictitious parent with an index greater than
3793:
3758:
3748:
3662:
3596:
3591:
3581:
3490:
3339:
3051:
2915:
2257:
523:
395:
3803:
3773:
3733:
3576:
3505:
3452:
3372:
3208:(14 October 2019). "Compact Fenwick trees for dynamic ranking and selection".
2681:
1942:
234:
2535:
indicating that the rank is not in the tree. (Depending on the application,
1976:
is stored or used. Excluding the fictitious nodes with indexes greater than
3808:
3768:
3615:
3543:
3533:
2584:
Each step, either the current node is a fictitious node (index greater than
3182:
24:
3697:
3387:
3813:
3687:
3667:
3640:
3625:
3377:
3117:
3798:
3702:
3677:
3620:
3467:
3397:
3392:
3367:
3300:
3295:
1956:
This conceptual tree is infinite, but only the part with indexes up to
3077:
3717:
3692:
3672:
3657:
3566:
3457:
3382:
1835:. This can be optimized by stopping at their first common ancestor.
400:
Given an array of values, it is sometimes desirable to calculate the
233:
is a data structure that can efficiently update values and calculate
2644:
the target is in its (empty) left subtree, return the current index.
2228:'s parent, then its grandparent, and so on, until the index exceeds
3214:
2473:
node, whose index is the greatest power of 2 less than or equal to
3561:
3462:
3417:
3252:
Halim, Steven; Halim, Felix; Effendy, Suhendry (3 December 2018).
1660:
1095:{\displaystyle i-\operatorname {lsb} (i)=i\mathbin {\&} (i-1)}
1934:{\displaystyle i+\operatorname {lsb} (i)=(i\mathbin {|} (i-1))+1}
1133:
of the tree contains nodes with indices corresponding to sums of
3553:
806:{\displaystyle \textstyle F=\sum A(i-\operatorname {lsb} (i),i]}
3304:
2651:
the target is in its right subtree, return the fallback index.
1635:
total descendants. (These numbers include nodes greater than
18:
2907:{\displaystyle {\text{lsb}}(10{\textbf {1}}00_{2})=100_{2}=4}
1429:{\displaystyle 3=2^{1}+2^{0},5=2^{2}+2^{0},6=2^{2}+2^{1},...}
1018:
The interrogation tree is defined so that the parent of node
515:{\displaystyle \operatorname {lsb} (i)=i\mathbin {\&} -i}
2914:. This function can be simply implemented in code through a
1596:{\displaystyle i+1,i+2,i+4,...,i+\operatorname {lsb} (i)/2}
3220:
Extensive discussion of practical implementation details.
414:
Fenwick trees are particularly designed to implement the
3256:. Vol. 1 (4th ed.). Lulu Press, Incorporated.
947:
may be considered to contain the sum of the empty range
300:
time. This is achieved by representing the values as a
747:
437:
An important function in this index arithmetic is the
2980:
2940:
2853:
2816:
2796:
2772:
2730:
2610:
2590:
2561:
2541:
2502:
2479:
2375:
2355:
2309:
2271:
2234:
2214:
2185:
2156:
2118:
2089:
2054:
2025:
2002:
1982:
1962:
1869:
1849:
1821:
1795:
1745:
1725:
1675:
1641:
1609:
1515:
1464:
1444:
1320:
1294:
1211:
1185:
1159:
1139:
1119:
1044:
1024:
953:
924:
883:
851:
819:
746:
714:
694:
674:
591:
567:
538:
479:
455:
357:
337:
310:
271:
250:
3726:
3605:
3552:
3481:
3338:
193:
186:
163:
140:
125:
114:
102:
94:
84:
68:
2995:
2966:
2906:
2839:
2802:
2778:
2747:
2625:
2596:
2573:
2547:
2508:
2485:
2439:
2361:
2341:
2295:
2240:
2220:
2200:
2171:
2139:
2104:
2075:
2040:
2008:
1988:
1968:
1933:
1855:
1827:
1807:
1781:
1731:
1711:
1647:
1627:
1595:
1502:{\displaystyle \log _{2}(\operatorname {lsb} (i))}
1501:
1450:
1428:
1306:
1280:
1197:
1171:
1145:
1125:
1094:
1030:
983:
939:
910:
866:
837:
805:
729:
700:
680:
660:
573:
553:
514:
461:
378:
343:
322:
292:
256:
2256:Unlike the other two trees, the search tree is a
1179:representing an empty sum 0). For example, level
1002:used for translating indexes to prefix sums, the
529:A Fenwick tree is most easily understood using a
911:{\displaystyle \operatorname {lsb} (0)=\infty ,}
3025:parentIndex := index + lsb(index)
2342:{\displaystyle i\pm \operatorname {lsb} (i)/2}
708:(inclusive). The corresponding Fenwick array
3316:
404:of values up to each index according to some
8:
2702:sum += tree index -= lsb(index)
978:
975:
629:
613:
3286:An article on Fenwick Trees on Algorithmist
1281:{\displaystyle 1=2^{0},2=2^{1},4=2^{2},...}
3323:
3309:
3301:
3291:An entry on Fenwick Trees on Polymath wiki
2721:tree += value index += lsb(index)
111:
76:
3213:
3172:
2979:
2956:
2939:
2892:
2876:
2866:
2865:
2854:
2852:
2847:, as shown in its binary representation:
2817:
2815:
2795:
2771:
2731:
2729:
2609:
2589:
2560:
2540:
2501:
2478:
2404:
2403:
2374:
2354:
2331:
2308:
2296:{\displaystyle \operatorname {lsb} (i)=1}
2270:
2233:
2213:
2184:
2155:
2117:
2088:
2053:
2024:
2001:
1981:
1961:
1901:
1900:
1868:
1848:
1820:
1794:
1744:
1724:
1674:
1655:, which are omitted and never accessed.)
1640:
1608:
1585:
1514:
1469:
1463:
1443:
1408:
1395:
1376:
1363:
1344:
1331:
1319:
1293:
1260:
1241:
1222:
1210:
1184:
1158:
1138:
1118:
1072:
1043:
1023:
1006:tree used for updating elements, and the
952:
923:
918:but the value is never actually needed.
882:
850:
818:
745:
713:
693:
673:
661:{\displaystyle A(i,j]=\{A\}_{k=i+1}^{j},}
649:
632:
590:
566:
537:
501:
478:
454:
356:
336:
309:
270:
249:
998:implicit trees over the same array: the
49:of all important aspects of the article.
3281:A tutorial on Fenwick Trees on TopCoder
3125:IEEE Transactions on Information Theory
3068:
1628:{\displaystyle \operatorname {lsb} (i)}
838:{\displaystyle \operatorname {lsb} (i)}
1945:). For example, the parent of 6 = 110
65:
45:Please consider expanding the lead to
1102:. For example, the parent of 6 = 110
7:
3154:
3152:
2450:For example, the children of 6 = 110
2867:
2641:If the current node is a leaf and:
2840:{\displaystyle {\text{lsb}}(20)=4}
1073:
902:
502:
14:
3161:Software: Practice and Experience
2581:might be used for this purpose.)
845:values ending with and including
445:operation. This is the greatest
3235:Combinatorial Algorithms, Part 1
2369:'s parent in the search tree is
1110:. Implicit node 0 is the root.
23:
3239:The Art of Computer Programming
3138:from the original on 2019-07-14
3098:from the original on 2019-07-17
2748:{\displaystyle {\text{lsb}}(n)}
1789:, subtract the prefix sums for
396:Prefix sums § Applications
37:may be too short to adequately
3118:"A fast on-line adaptive code"
2990:
2984:
2961:
2944:
2882:
2859:
2828:
2822:
2786:or, equivalently, the largest
2742:
2736:
2620:
2614:
2434:
2431:
2425:
2410:
2405:
2400:
2397:
2391:
2376:
2328:
2322:
2284:
2278:
2195:
2189:
2166:
2160:
2134:
2122:
2099:
2093:
2070:
2058:
2035:
2029:
1922:
1919:
1907:
1902:
1894:
1888:
1882:
1776:
1770:
1755:
1749:
1706:
1700:
1685:
1679:
1622:
1616:
1582:
1576:
1496:
1493:
1487:
1478:
1089:
1077:
1063:
1057:
969:
957:
934:
928:
896:
890:
861:
855:
832:
826:
799:
790:
784:
769:
757:
751:
724:
718:
625:
619:
607:
595:
548:
542:
492:
486:
373:
361:
287:
275:
47:provide an accessible overview
1:
994:A "Fenwick tree" is actually
3029:parentIndex < size(tree)
2967:{\displaystyle O(n\log {n})}
2150:To modify one of the values
2710:update(tree, index, value)
2462:, and its parent is 4 = 100
1782:{\displaystyle A+\cdots +A}
1712:{\displaystyle A+\cdots +A}
1153:distinct powers of 2 (with
984:{\displaystyle A(0,0]=\{\}}
3861:
3003:construction is possible:
2790:that is also a divisor of
393:
439:least significant set bit
379:{\displaystyle O(\log n)}
293:{\displaystyle O(\log n)}
110:
75:
3779:Left-child right-sibling
3013:tree := values
2533:special "overflow" value
3835:Trees (data structures)
3609:data partitioning trees
3567:C-trie (compressed ADT)
3254:Competitive Programming
2656:If the current node is
2260:, arranged in an order
1669:To find the prefix sum
813:. That is, the sum of
449:which divides an index
237:in an array of values.
3183:10.1002/spe.4380240306
2997:
2968:
2908:
2841:
2804:
2780:
2749:
2717:index < size(tree)
2627:
2598:
2575:
2549:
2510:
2487:
2441:
2363:
2343:
2297:
2242:
2222:
2202:
2173:
2141:
2140:{\displaystyle A(0,8]}
2106:
2077:
2076:{\displaystyle A(4,6]}
2042:
2010:
1990:
1970:
1935:
1857:
1829:
1809:
1783:
1733:
1713:
1666:
1649:
1629:
1597:
1503:
1452:
1430:
1308:
1282:
1199:
1173:
1147:
1127:
1096:
1032:
1014:The interrogation tree
985:
941:
912:
868:
839:
807:
731:
702:
682:
662:
575:
555:
516:
463:
420:cumulative probability
380:
345:
324:
294:
258:
3116:Boris Ryabko (1992).
3078:"A fast on-line code"
3076:Boris Ryabko (1989).
2998:
2969:
2920:lsb(n) = n & (-n)
2909:
2842:
2805:
2781:
2750:
2628:
2599:
2576:
2550:
2511:
2488:
2442:
2364:
2344:
2298:
2243:
2223:
2203:
2174:
2142:
2107:
2078:
2043:
2011:
1991:
1971:
1936:
1858:
1830:
1810:
1784:
1734:
1714:
1664:
1650:
1630:
1598:
1504:
1453:
1431:
1309:
1283:
1200:
1174:
1148:
1128:
1097:
1033:
986:
942:
913:
869:
840:
808:
732:
703:
683:
663:
576:
556:
522:(where & denotes
517:
464:
430:A Fenwick tree is an
381:
346:
325:
295:
259:
3789:Log-structured merge
3332:Tree data structures
3047:Order statistic tree
2996:{\displaystyle O(n)}
2978:
2938:
2851:
2814:
2794:
2770:
2728:
2608:
2588:
2559:
2539:
2500:
2477:
2373:
2353:
2307:
2269:
2232:
2212:
2183:
2179:, add the change to
2154:
2116:
2087:
2052:
2023:
2000:
1980:
1960:
1867:
1847:
1819:
1793:
1743:
1723:
1719:, sum the values in
1673:
1639:
1607:
1513:
1462:
1442:
1318:
1292:
1209:
1183:
1157:
1137:
1117:
1042:
1022:
951:
922:
881:
849:
817:
744:
712:
692:
672:
589:
565:
536:
477:
453:
355:
335:
308:
269:
248:
3204:Marchini, Stefano;
3017:every index, value
2690:query(tree, index)
2574:{\displaystyle n+1}
1808:{\displaystyle i-1}
1307:{\displaystyle k=2}
1198:{\displaystyle k=1}
1172:{\displaystyle k=0}
654:
323:{\displaystyle n+1}
228:binary indexed tree
71:Binary indexed tree
3845:Russian inventions
3754:Fractal tree index
3349:associative arrays
3033:tree += value
3009:construct(values)
2993:
2964:
2904:
2837:
2800:
2776:
2745:
2694:sum := 0
2623:
2594:
2571:
2545:
2506:
2483:
2437:
2359:
2339:
2293:
2238:
2218:
2198:
2169:
2137:
2102:
2073:
2038:
2006:
1986:
1966:
1931:
1853:
1825:
1805:
1779:
1729:
1709:
1667:
1645:
1625:
1593:
1499:
1448:
1426:
1304:
1278:
1195:
1169:
1143:
1123:
1092:
1028:
1000:interrogation tree
981:
937:
908:
864:
835:
803:
802:
727:
698:
678:
658:
628:
583:half-open interval
571:
551:
512:
459:
441:, also called the
376:
341:
320:
290:
254:
3840:Soviet inventions
3822:
3821:
3206:Vigna, Sebastiano
3085:Soviet Math. Dokl
2869:
2857:
2820:
2803:{\displaystyle n}
2779:{\displaystyle n}
2758:least significant
2734:
2647:it is fictitious
2626:{\displaystyle F}
2597:{\displaystyle n}
2548:{\displaystyle 0}
2509:{\displaystyle n}
2486:{\displaystyle n}
2362:{\displaystyle i}
2241:{\displaystyle n}
2221:{\displaystyle i}
2201:{\displaystyle F}
2172:{\displaystyle A}
2112:holds the sum of
2105:{\displaystyle F}
2048:holds the sum of
2041:{\displaystyle F}
2009:{\displaystyle n}
1989:{\displaystyle n}
1969:{\displaystyle n}
1941:(where | denotes
1856:{\displaystyle i}
1828:{\displaystyle j}
1732:{\displaystyle i}
1648:{\displaystyle n}
1451:{\displaystyle i}
1146:{\displaystyle k}
1126:{\displaystyle k}
1031:{\displaystyle i}
940:{\displaystyle F}
867:{\displaystyle A}
730:{\displaystyle F}
701:{\displaystyle j}
681:{\displaystyle i}
574:{\displaystyle n}
554:{\displaystyle A}
462:{\displaystyle i}
416:arithmetic coding
344:{\displaystyle n}
257:{\displaystyle n}
220:
219:
216:
215:
64:
63:
3852:
3325:
3318:
3311:
3302:
3268:
3267:
3249:
3243:
3242:
3227:
3221:
3219:
3217:
3201:
3195:
3194:
3176:
3156:
3147:
3146:
3144:
3143:
3137:
3131:(1): 1400–1404.
3122:
3113:
3107:
3106:
3104:
3103:
3097:
3082:
3073:
3002:
3000:
2999:
2994:
2973:
2971:
2970:
2965:
2960:
2921:
2913:
2911:
2910:
2905:
2897:
2896:
2881:
2880:
2871:
2870:
2858:
2855:
2846:
2844:
2843:
2838:
2821:
2818:
2809:
2807:
2806:
2801:
2785:
2783:
2782:
2777:
2754:
2752:
2751:
2746:
2735:
2732:
2632:
2630:
2629:
2624:
2603:
2601:
2600:
2595:
2580:
2578:
2577:
2572:
2554:
2552:
2551:
2546:
2515:
2513:
2512:
2507:
2492:
2490:
2489:
2484:
2446:
2444:
2443:
2438:
2409:
2408:
2368:
2366:
2365:
2360:
2348:
2346:
2345:
2340:
2335:
2302:
2300:
2299:
2294:
2247:
2245:
2244:
2239:
2227:
2225:
2224:
2219:
2207:
2205:
2204:
2199:
2178:
2176:
2175:
2170:
2146:
2144:
2143:
2138:
2111:
2109:
2108:
2103:
2082:
2080:
2079:
2074:
2047:
2045:
2044:
2039:
2015:
2013:
2012:
2007:
1995:
1993:
1992:
1987:
1975:
1973:
1972:
1967:
1940:
1938:
1937:
1932:
1906:
1905:
1862:
1860:
1859:
1854:
1834:
1832:
1831:
1826:
1814:
1812:
1811:
1806:
1788:
1786:
1785:
1780:
1738:
1736:
1735:
1730:
1718:
1716:
1715:
1710:
1654:
1652:
1651:
1646:
1634:
1632:
1631:
1626:
1602:
1600:
1599:
1594:
1589:
1508:
1506:
1505:
1500:
1474:
1473:
1457:
1455:
1454:
1449:
1435:
1433:
1432:
1427:
1413:
1412:
1400:
1399:
1381:
1380:
1368:
1367:
1349:
1348:
1336:
1335:
1313:
1311:
1310:
1305:
1287:
1285:
1284:
1279:
1265:
1264:
1246:
1245:
1227:
1226:
1204:
1202:
1201:
1196:
1178:
1176:
1175:
1170:
1152:
1150:
1149:
1144:
1132:
1130:
1129:
1124:
1101:
1099:
1098:
1093:
1076:
1037:
1035:
1034:
1029:
990:
988:
987:
982:
946:
944:
943:
938:
917:
915:
914:
909:
873:
871:
870:
865:
844:
842:
841:
836:
812:
810:
809:
804:
736:
734:
733:
728:
707:
705:
704:
699:
687:
685:
684:
679:
667:
665:
664:
659:
653:
648:
580:
578:
577:
572:
560:
558:
557:
552:
521:
519:
518:
513:
505:
471:two's complement
468:
466:
465:
460:
409:binary operation
385:
383:
382:
377:
350:
348:
347:
342:
329:
327:
326:
321:
299:
297:
296:
291:
263:
261:
260:
255:
212:
203:
188:Space complexity
182:
173:
159:
150:
112:
80:
66:
59:
56:
50:
27:
19:
3860:
3859:
3855:
3854:
3853:
3851:
3850:
3849:
3825:
3824:
3823:
3818:
3722:
3601:
3548:
3477:
3473:Weight-balanced
3428:Order statistic
3342:
3334:
3329:
3277:
3272:
3271:
3264:
3251:
3250:
3246:
3229:
3228:
3224:
3203:
3202:
3198:
3158:
3157:
3150:
3141:
3139:
3135:
3120:
3115:
3114:
3110:
3101:
3099:
3095:
3080:
3075:
3074:
3070:
3065:
3043:
3038:
2976:
2975:
2936:
2935:
2932:
2919:
2888:
2872:
2849:
2848:
2812:
2811:
2810:. For example,
2792:
2791:
2768:
2767:
2726:
2725:
2722:
2678:
2606:
2605:
2586:
2585:
2557:
2556:
2537:
2536:
2498:
2497:
2475:
2474:
2465:
2461:
2457:
2453:
2371:
2370:
2351:
2350:
2305:
2304:
2267:
2266:
2254:
2252:The search tree
2230:
2229:
2210:
2209:
2181:
2180:
2152:
2151:
2114:
2113:
2085:
2084:
2050:
2049:
2021:
2020:
1998:
1997:
1978:
1977:
1958:
1957:
1952:
1948:
1865:
1864:
1845:
1844:
1841:
1839:The update tree
1817:
1816:
1791:
1790:
1741:
1740:
1721:
1720:
1671:
1670:
1637:
1636:
1605:
1604:
1511:
1510:
1465:
1460:
1459:
1440:
1439:
1404:
1391:
1372:
1359:
1340:
1327:
1316:
1315:
1314:contains nodes
1290:
1289:
1256:
1237:
1218:
1207:
1206:
1205:contains nodes
1181:
1180:
1155:
1154:
1135:
1134:
1115:
1114:
1109:
1105:
1040:
1039:
1020:
1019:
1016:
949:
948:
920:
919:
879:
878:
847:
846:
815:
814:
742:
741:
710:
709:
690:
689:
688:(exclusive) to
670:
669:
668:the range from
587:
586:
581:values. Using
563:
562:
534:
533:
531:one-based array
475:
474:
451:
450:
428:
398:
392:
386:node accesses.
353:
352:
333:
332:
306:
305:
267:
266:
246:
245:
206:
197:
176:
167:
153:
144:
116:Time complexity
70:
60:
54:
51:
44:
32:This article's
28:
17:
12:
11:
5:
3858:
3856:
3848:
3847:
3842:
3837:
3827:
3826:
3820:
3819:
3817:
3816:
3811:
3806:
3801:
3796:
3791:
3786:
3781:
3776:
3771:
3766:
3761:
3756:
3751:
3746:
3741:
3736:
3730:
3728:
3724:
3723:
3721:
3720:
3715:
3710:
3705:
3700:
3695:
3690:
3685:
3680:
3675:
3670:
3665:
3660:
3655:
3638:
3633:
3628:
3623:
3618:
3612:
3610:
3603:
3602:
3600:
3599:
3594:
3589:
3587:Ternary search
3584:
3579:
3574:
3569:
3564:
3558:
3556:
3550:
3549:
3547:
3546:
3541:
3536:
3531:
3526:
3521:
3516:
3511:
3503:
3498:
3493:
3487:
3485:
3479:
3478:
3476:
3475:
3470:
3465:
3460:
3455:
3450:
3445:
3435:
3430:
3425:
3420:
3415:
3410:
3400:
3395:
3390:
3385:
3380:
3375:
3370:
3365:
3360:
3354:
3352:
3336:
3335:
3330:
3328:
3327:
3320:
3313:
3305:
3299:
3298:
3296:stack exchange
3293:
3288:
3283:
3276:
3275:External links
3273:
3270:
3269:
3262:
3244:
3222:
3196:
3174:10.1.1.14.8917
3167:(3): 327–336.
3148:
3108:
3091:(3): 533–537.
3067:
3066:
3064:
3061:
3060:
3059:
3054:
3049:
3042:
3039:
3005:
2992:
2989:
2986:
2983:
2963:
2959:
2955:
2952:
2949:
2946:
2943:
2931:
2928:
2924:signed integer
2903:
2900:
2895:
2891:
2887:
2884:
2879:
2875:
2864:
2861:
2836:
2833:
2830:
2827:
2824:
2799:
2775:
2744:
2741:
2738:
2686:
2677:
2674:
2673:
2672:
2671:
2670:
2667:
2664:
2654:
2653:
2652:
2645:
2622:
2619:
2616:
2613:
2593:
2570:
2567:
2564:
2544:
2505:
2482:
2463:
2459:
2455:
2451:
2436:
2433:
2430:
2427:
2424:
2421:
2418:
2415:
2412:
2407:
2402:
2399:
2396:
2393:
2390:
2387:
2384:
2381:
2378:
2358:
2338:
2334:
2330:
2327:
2324:
2321:
2318:
2315:
2312:
2292:
2289:
2286:
2283:
2280:
2277:
2274:
2253:
2250:
2237:
2217:
2197:
2194:
2191:
2188:
2168:
2165:
2162:
2159:
2136:
2133:
2130:
2127:
2124:
2121:
2101:
2098:
2095:
2092:
2072:
2069:
2066:
2063:
2060:
2057:
2037:
2034:
2031:
2028:
2005:
1985:
1965:
1950:
1946:
1930:
1927:
1924:
1921:
1918:
1915:
1912:
1909:
1904:
1899:
1896:
1893:
1890:
1887:
1884:
1881:
1878:
1875:
1872:
1852:
1840:
1837:
1824:
1804:
1801:
1798:
1778:
1775:
1772:
1769:
1766:
1763:
1760:
1757:
1754:
1751:
1748:
1728:
1708:
1705:
1702:
1699:
1696:
1693:
1690:
1687:
1684:
1681:
1678:
1644:
1624:
1621:
1618:
1615:
1612:
1592:
1588:
1584:
1581:
1578:
1575:
1572:
1569:
1566:
1563:
1560:
1557:
1554:
1551:
1548:
1545:
1542:
1539:
1536:
1533:
1530:
1527:
1524:
1521:
1518:
1498:
1495:
1492:
1489:
1486:
1483:
1480:
1477:
1472:
1468:
1447:
1425:
1422:
1419:
1416:
1411:
1407:
1403:
1398:
1394:
1390:
1387:
1384:
1379:
1375:
1371:
1366:
1362:
1358:
1355:
1352:
1347:
1343:
1339:
1334:
1330:
1326:
1323:
1303:
1300:
1297:
1277:
1274:
1271:
1268:
1263:
1259:
1255:
1252:
1249:
1244:
1240:
1236:
1233:
1230:
1225:
1221:
1217:
1214:
1194:
1191:
1188:
1168:
1165:
1162:
1142:
1122:
1107:
1103:
1091:
1088:
1085:
1082:
1079:
1075:
1071:
1068:
1065:
1062:
1059:
1056:
1053:
1050:
1047:
1027:
1015:
1012:
991:with value 0.
980:
977:
974:
971:
968:
965:
962:
959:
956:
936:
933:
930:
927:
907:
904:
901:
898:
895:
892:
889:
886:
863:
860:
857:
854:
834:
831:
828:
825:
822:
801:
798:
795:
792:
789:
786:
783:
780:
777:
774:
771:
768:
765:
762:
759:
756:
753:
750:
726:
723:
720:
717:
697:
677:
657:
652:
647:
644:
641:
638:
635:
631:
627:
624:
621:
618:
615:
612:
609:
606:
603:
600:
597:
594:
570:
550:
547:
544:
541:
511:
508:
504:
500:
497:
494:
491:
488:
485:
482:
473:arithmetic as
458:
443:find first set
427:
424:
394:Main article:
391:
388:
375:
372:
369:
366:
363:
360:
340:
319:
316:
313:
289:
286:
283:
280:
277:
274:
253:
218:
217:
214:
213:
204:
195:
191:
190:
184:
183:
174:
165:
161:
160:
151:
142:
138:
137:
132:
127:
123:
122:
120:big O notation
108:
107:
104:
100:
99:
96:
92:
91:
88:
82:
81:
73:
72:
62:
61:
41:the key points
31:
29:
22:
16:Data structure
15:
13:
10:
9:
6:
4:
3:
2:
3857:
3846:
3843:
3841:
3838:
3836:
3833:
3832:
3830:
3815:
3812:
3810:
3807:
3805:
3802:
3800:
3797:
3795:
3792:
3790:
3787:
3785:
3782:
3780:
3777:
3775:
3772:
3770:
3767:
3765:
3764:Hash calendar
3762:
3760:
3757:
3755:
3752:
3750:
3747:
3745:
3742:
3740:
3737:
3735:
3732:
3731:
3729:
3725:
3719:
3716:
3714:
3711:
3709:
3706:
3704:
3701:
3699:
3696:
3694:
3691:
3689:
3686:
3684:
3681:
3679:
3676:
3674:
3671:
3669:
3666:
3664:
3661:
3659:
3656:
3653:
3651:
3645:
3643:
3639:
3637:
3634:
3632:
3629:
3627:
3624:
3622:
3619:
3617:
3614:
3613:
3611:
3608:
3604:
3598:
3595:
3593:
3590:
3588:
3585:
3583:
3580:
3578:
3575:
3573:
3570:
3568:
3565:
3563:
3560:
3559:
3557:
3555:
3551:
3545:
3542:
3540:
3539:van Emde Boas
3537:
3535:
3532:
3530:
3529:Skew binomial
3527:
3525:
3522:
3520:
3517:
3515:
3512:
3510:
3508:
3504:
3502:
3499:
3497:
3494:
3492:
3489:
3488:
3486:
3484:
3480:
3474:
3471:
3469:
3466:
3464:
3461:
3459:
3456:
3454:
3451:
3449:
3446:
3444:
3440:
3436:
3434:
3431:
3429:
3426:
3424:
3421:
3419:
3416:
3414:
3411:
3409:
3408:Binary search
3405:
3401:
3399:
3396:
3394:
3391:
3389:
3386:
3384:
3381:
3379:
3376:
3374:
3371:
3369:
3366:
3364:
3361:
3359:
3356:
3355:
3353:
3350:
3346:
3341:
3337:
3333:
3326:
3321:
3319:
3314:
3312:
3307:
3306:
3303:
3297:
3294:
3292:
3289:
3287:
3284:
3282:
3279:
3278:
3274:
3265:
3263:9781716745522
3259:
3255:
3248:
3245:
3240:
3236:
3232:
3231:Knuth, Donald
3226:
3223:
3216:
3211:
3207:
3200:
3197:
3192:
3188:
3184:
3180:
3175:
3170:
3166:
3162:
3155:
3153:
3149:
3134:
3130:
3126:
3119:
3112:
3109:
3094:
3090:
3086:
3079:
3072:
3069:
3062:
3058:
3055:
3053:
3050:
3048:
3045:
3044:
3040:
3036:
3032:
3028:
3024:
3020:
3016:
3012:
3008:
3004:
2987:
2981:
2974:time, but an
2957:
2953:
2950:
2947:
2941:
2929:
2927:
2925:
2922:, assuming a
2917:
2901:
2898:
2893:
2889:
2885:
2877:
2873:
2862:
2834:
2831:
2825:
2797:
2789:
2773:
2766:of the given
2765:
2761:
2760:1-bit
2759:
2755:computes the
2739:
2724:The function
2720:
2716:
2713:
2709:
2705:
2701:
2698:index > 0
2697:
2693:
2689:
2685:
2683:
2675:
2668:
2665:
2662:
2661:
2659:
2655:
2650:
2646:
2643:
2642:
2640:
2639:
2638:
2635:
2617:
2611:
2591:
2582:
2568:
2565:
2562:
2542:
2534:
2529:
2526:
2521:
2517:
2503:
2494:
2480:
2472:
2467:
2448:
2428:
2422:
2419:
2416:
2413:
2394:
2388:
2385:
2382:
2379:
2356:
2336:
2332:
2325:
2319:
2316:
2313:
2310:
2290:
2287:
2281:
2275:
2272:
2263:
2259:
2251:
2249:
2235:
2215:
2192:
2186:
2163:
2157:
2148:
2147:, and so on.
2131:
2128:
2125:
2119:
2096:
2090:
2067:
2064:
2061:
2055:
2032:
2026:
2017:
2003:
1983:
1963:
1954:
1944:
1928:
1925:
1916:
1913:
1910:
1897:
1891:
1885:
1879:
1876:
1873:
1870:
1850:
1838:
1836:
1822:
1802:
1799:
1796:
1773:
1767:
1764:
1761:
1758:
1752:
1746:
1726:
1703:
1697:
1694:
1691:
1688:
1682:
1676:
1663:
1659:
1656:
1642:
1619:
1613:
1610:
1590:
1586:
1579:
1573:
1570:
1567:
1564:
1561:
1558:
1555:
1552:
1549:
1546:
1543:
1540:
1537:
1534:
1531:
1528:
1525:
1522:
1519:
1516:
1490:
1484:
1481:
1475:
1470:
1466:
1445:
1436:
1423:
1420:
1417:
1414:
1409:
1405:
1401:
1396:
1392:
1388:
1385:
1382:
1377:
1373:
1369:
1364:
1360:
1356:
1353:
1350:
1345:
1341:
1337:
1332:
1328:
1324:
1321:
1301:
1298:
1295:
1275:
1272:
1269:
1266:
1261:
1257:
1253:
1250:
1247:
1242:
1238:
1234:
1231:
1228:
1223:
1219:
1215:
1212:
1192:
1189:
1186:
1166:
1163:
1160:
1140:
1120:
1111:
1086:
1083:
1080:
1069:
1066:
1060:
1054:
1051:
1048:
1045:
1025:
1013:
1011:
1009:
1005:
1001:
997:
992:
972:
966:
963:
960:
954:
931:
925:
905:
899:
893:
887:
884:
875:
858:
852:
829:
823:
820:
796:
793:
787:
781:
778:
775:
772:
766:
763:
760:
754:
748:
740:
721:
715:
695:
675:
655:
650:
645:
642:
639:
636:
633:
622:
616:
610:
604:
601:
598:
592:
584:
568:
545:
539:
532:
527:
525:
509:
506:
498:
495:
489:
483:
480:
472:
456:
448:
444:
440:
435:
433:
432:implicit tree
425:
423:
421:
417:
412:
410:
407:
403:
402:running total
397:
389:
387:
370:
367:
364:
358:
338:
317:
314:
311:
303:
284:
281:
278:
272:
265:performed in
251:
242:
238:
236:
232:
229:
225:
210:
205:
201:
196:
192:
189:
185:
180:
175:
171:
166:
162:
157:
152:
148:
143:
139:
136:
133:
131:
128:
124:
121:
117:
113:
109:
105:
101:
97:
93:
90:Binomial tree
89:
87:
83:
79:
74:
67:
58:
48:
42:
40:
35:
30:
26:
21:
20:
3743:
3649:
3641:
3506:
3439:Left-leaning
3345:dynamic sets
3340:Search trees
3253:
3247:
3234:
3225:
3199:
3164:
3160:
3140:. Retrieved
3128:
3124:
3111:
3100:. Retrieved
3088:
3084:
3071:
3057:Segment tree
3034:
3030:
3026:
3022:
3018:
3014:
3010:
3006:
2933:
2930:Construction
2788:power of two
2764:last set bit
2763:
2756:
2723:
2718:
2714:
2711:
2707:
2703:
2699:
2695:
2691:
2687:
2679:
2660:a leaf and:
2657:
2648:
2636:
2583:
2530:
2524:
2522:
2518:
2495:
2470:
2468:
2449:
2255:
2149:
2018:
1955:
1842:
1668:
1657:
1437:
1112:
1017:
1007:
1003:
999:
995:
993:
876:
585:syntax, let
528:
447:power of two
438:
436:
429:
413:
399:
243:
239:
230:
227:
224:Fenwick tree
223:
221:
208:
199:
178:
169:
155:
146:
134:
129:
106:Boris Ryabko
69:Fenwick tree
52:
36:
34:lead section
3739:Exponential
3727:Other trees
3052:Prefix sums
2926:data type.
2918:operation:
2916:bitwise AND
2458:and 7 = 111
2454:are 5 = 101
2258:binary tree
1949:is 8 = 1000
1113:Each level
1008:search tree
737:stores the
524:bitwise AND
426:Description
406:associative
235:prefix sums
103:Invented by
3829:Categories
3683:Priority R
3433:Palindrome
3215:1904.12370
3142:2019-07-14
3102:2019-07-17
3063:References
2682:pseudocode
2676:Pseudocode
2349:. Node
1943:bitwise OR
1509:children (
1288:and level
1106:is 4 = 100
739:range sums
390:Motivation
135:Worst case
3769:iDistance
3648:implicit
3636:Hilbert R
3631:Cartesian
3514:Fibonacci
3448:Scapegoat
3443:Red–black
3169:CiteSeerX
2954:
2680:A simple
2423:
2417:⋅
2389:
2383:−
2320:
2314:±
2276:
1914:−
1880:
1800:−
1762:⋯
1692:⋯
1614:
1574:
1485:
1476:
1084:−
1074:&
1055:
1049:−
903:∞
888:
824:
782:
776:−
764:∑
507:−
503:&
484:
368:
282:
126:Operation
55:July 2023
39:summarize
3784:Link/cut
3496:Binomial
3423:Interval
3233:(2011).
3133:Archived
3093:Archived
3041:See also
3007:function
2708:function
2688:function
2525:downward
2471:existing
95:Invented
3744:Fenwick
3708:Segment
3607:Spatial
3524:Pairing
3519:Leftist
3441:)
3413:Dancing
3406:)
3404:Optimal
3191:7519761
2208:, then
1603:), and
130:Average
3794:Merkle
3759:Fusion
3749:Finger
3673:Octree
3663:Metric
3597:Y-fast
3592:X-fast
3582:Suffix
3501:Brodal
3491:Binary
3260:
3189:
3171:
3035:return
2704:return
1004:update
164:Insert
141:Search
3804:Range
3774:K-ary
3734:Cover
3577:Radix
3562:Ctrie
3554:Tries
3483:Heaps
3463:Treap
3453:Splay
3418:HTree
3373:(a,b)
3363:2–3–4
3210:arXiv
3187:S2CID
3136:(PDF)
3121:(PDF)
3096:(PDF)
3081:(PDF)
3037:tree
3021:tree
2715:while
2696:while
2262:Knuth
1438:Node
996:three
561:with
304:with
231:(BIT)
194:Space
177:O(log
168:O(log
154:O(log
145:O(log
3809:SPQR
3688:Quad
3616:Ball
3572:Hash
3544:Weak
3534:Skew
3509:-ary
3258:ISBN
3031:then
2706:sum
1815:and
1458:has
302:tree
98:1989
86:Type
3814:Top
3668:MVP
3626:BSP
3378:AVL
3358:2–3
3179:doi
3015:for
2951:log
2890:100
2856:lsb
2819:lsb
2762:or
2733:lsb
2658:not
2555:or
2420:lsb
2386:lsb
2317:lsb
2273:lsb
1877:lsb
1863:is
1611:lsb
1571:lsb
1482:lsb
1467:log
1052:lsb
1038:is
885:lsb
821:lsb
779:lsb
526:).
481:lsb
365:log
279:log
226:or
118:in
3831::
3799:PQ
3713:VP
3703:R*
3698:R+
3678:PH
3652:-d
3644:-d
3621:BK
3468:UB
3393:B*
3388:B+
3368:AA
3237:.
3185:.
3177:.
3165:24
3163:.
3151:^
3129:28
3127:.
3123:.
3089:39
3087:.
3083:.
3027:if
3023:do
3019:in
3011:is
2874:00
2863:10
2826:20
2719:do
2712:is
2700:do
2692:is
2649:or
2493:.
2466:.
2447:.
2248:.
2083:,
2016:.
1953:.
874:.
222:A
207:O(
198:O(
3718:X
3693:R
3658:M
3654:)
3650:k
3646:(
3642:k
3507:d
3458:T
3437:(
3402:(
3398:B
3383:B
3351:)
3347:/
3343:(
3324:e
3317:t
3310:v
3266:.
3218:.
3212::
3193:.
3181::
3145:.
3105:.
2991:)
2988:n
2985:(
2982:O
2962:)
2958:n
2948:n
2945:(
2942:O
2902:4
2899:=
2894:2
2886:=
2883:)
2878:2
2868:1
2860:(
2835:4
2832:=
2829:)
2823:(
2798:n
2774:n
2743:)
2740:n
2737:(
2621:]
2618:i
2615:[
2612:F
2592:n
2569:1
2566:+
2563:n
2543:0
2504:n
2481:n
2464:2
2460:2
2456:2
2452:2
2435:)
2432:)
2429:i
2426:(
2414:2
2411:(
2406:|
2401:)
2398:)
2395:i
2392:(
2380:i
2377:(
2357:i
2337:2
2333:/
2329:)
2326:i
2323:(
2311:i
2291:1
2288:=
2285:)
2282:i
2279:(
2265:(
2236:n
2216:i
2196:]
2193:i
2190:[
2187:F
2167:]
2164:i
2161:[
2158:A
2135:]
2132:8
2129:,
2126:0
2123:(
2120:A
2100:]
2097:8
2094:[
2091:F
2071:]
2068:6
2065:,
2062:4
2059:(
2056:A
2036:]
2033:6
2030:[
2027:F
2004:n
1984:n
1964:n
1951:2
1947:2
1929:1
1926:+
1923:)
1920:)
1917:1
1911:i
1908:(
1903:|
1898:i
1895:(
1892:=
1889:)
1886:i
1883:(
1874:+
1871:i
1851:i
1823:j
1803:1
1797:i
1777:]
1774:j
1771:[
1768:A
1765:+
1759:+
1756:]
1753:i
1750:[
1747:A
1727:i
1707:]
1704:i
1701:[
1698:A
1695:+
1689:+
1686:]
1683:1
1680:[
1677:A
1643:n
1623:)
1620:i
1617:(
1591:2
1587:/
1583:)
1580:i
1577:(
1568:+
1565:i
1562:,
1559:.
1556:.
1553:.
1550:,
1547:4
1544:+
1541:i
1538:,
1535:2
1532:+
1529:i
1526:,
1523:1
1520:+
1517:i
1497:)
1494:)
1491:i
1488:(
1479:(
1471:2
1446:i
1424:.
1421:.
1418:.
1415:,
1410:1
1406:2
1402:+
1397:2
1393:2
1389:=
1386:6
1383:,
1378:0
1374:2
1370:+
1365:2
1361:2
1357:=
1354:5
1351:,
1346:0
1342:2
1338:+
1333:1
1329:2
1325:=
1322:3
1302:2
1299:=
1296:k
1276:.
1273:.
1270:.
1267:,
1262:2
1258:2
1254:=
1251:4
1248:,
1243:1
1239:2
1235:=
1232:2
1229:,
1224:0
1220:2
1216:=
1213:1
1193:1
1190:=
1187:k
1167:0
1164:=
1161:k
1141:k
1121:k
1108:2
1104:2
1090:)
1087:1
1081:i
1078:(
1070:i
1067:=
1064:)
1061:i
1058:(
1046:i
1026:i
979:}
976:{
973:=
970:]
967:0
964:,
961:0
958:(
955:A
935:]
932:0
929:[
926:F
906:,
900:=
897:)
894:0
891:(
862:]
859:i
856:[
853:A
833:)
830:i
827:(
800:]
797:i
794:,
791:)
788:i
785:(
773:i
770:(
767:A
761:=
758:]
755:i
752:[
749:F
725:]
722:n
719:[
716:F
696:j
676:i
656:,
651:j
646:1
643:+
640:i
637:=
634:k
630:}
626:]
623:k
620:[
617:A
614:{
611:=
608:]
605:j
602:,
599:i
596:(
593:A
569:n
549:]
546:n
543:[
540:A
510:i
499:i
496:=
493:)
490:i
487:(
457:i
374:)
371:n
362:(
359:O
339:n
318:1
315:+
312:n
288:)
285:n
276:(
273:O
252:n
211:)
209:n
202:)
200:n
181:)
179:n
172:)
170:n
158:)
156:n
149:)
147:n
57:)
53:(
43:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
