A pure-rust(with zero dependencies) fenwick tree, for the efficient computation of dynamic prefix sums.

Related tags

Learning Resources ftree
Overview

indexset

crates.io docs

A pure-rust(with zero dependencies, no-std) fenwick tree, for the efficient computation of dynamic prefix sums.

Background

Did you ever have to keep track of a sum, and update it at the same time?

Let's say that you have an array that represents the lengths of some other containers: [1, 6, 3, 9, 2]

What if you want to get the sum up until the n-th element? In the worst-case, this will take O(n) time. Updating on the other hand, is simply a matter of incrementing at the specified index, at O(1).

A fenwick tree allows you to both get the sum and do updates in O(log n) time.

Moreover, let's assume that you want to get the index of the first value such that <= sum.

Without using a Fenwick tree, this would take (n * log n) time (a binary search with the sum being computed during each iteration). Using one however, only takes O(log n) time. This might seem like a very niche need, and it is. It is utilized in the indexset crate, a two-level B-Tree, to very efficiently support vector-like indexing by position.

Performance

It's very performant. I have searched all over codeforces for all competitive programming fenwick tree performance tricks that there are, and put them all in this crate.

Naming

This library is called ftree, because the base data structure is FenwickTree.

Changelog

See CHANGELOG.md.

You might also like...
Rust library for concurrent data access, using memory-mapped files, zero-copy deserialization, and wait-free synchronization.

mmap-sync mmap-sync is a Rust crate designed to manage high-performance, concurrent data access between a single writer process and multiple reader pr

Cloudflare 97 Jun 26, 2023
A HashMap/Vector hybrid: efficient, ordered key-value data storage in Rust.

hashvec A HashVec is a hash map / dictionary whose key-value pairs are stored (and can be iterated over) in a fixed order, by default the order in whi

Skye Terran 2 May 16, 2022
An efficient runtime for asynchronous applications in Rust.

PhotonIO PhotonIO is an efficient runtime for asynchronous applications in Rust. Features Asynchronous filesystem and networking I/O for Linux based o

PhotonDB 40 Jan 4, 2023
A turing-complete programming language using only zero-width unicode characters, inspired by brainfuck and whitespace.

Zero-Width A turing-complete programming language using only zero-width unicode characters, inspired by brainfuck and whitespace. Currently a (possibl

Gavin M 2 Jan 14, 2022
Curdleproofs is a zero-knowledge shuffle argument
Curdleproofs is a zero-knowledge shuffle argument

Curdleproofs Curdleproofs is a zero-knowledge shuffle argument inspired by BG12. Zero-knowledge shuffle arguments can have multiple use cases: Secret

George Kadianakis 43 Dec 10, 2022
A minimal and fast zero-copy parser for the PE32+ file format.

peview A minimal and fast zero-copy parser for the PE32+ file format. Goal This project aims to offer a more light weight and easier to use alternativ

null 5 Dec 20, 2022
Zero-copy, no-std proquint encoding and decoding

proqnt A pronounceable quintuplet, or proquint, is a pronounceable 5-letter string encoding a unique 16-bit integer. Proquints may be used to encode b

Jad Ghalayini 11 May 9, 2023
Simple, automatic, and customizable tree pretty-printing in Rust.
Simple, automatic, and customizable tree pretty-printing in Rust.

display_tree Simple, automatic, and customizable tree pretty-printing in Rust. This crate provides tools to easily pretty-print data as a tree, includ

Cameron Delong 20 Dec 24, 2022
Use rust programming language to create a b+ tree.
Use rust programming language to create a b+ tree.

Use rust programming language to create a b+ tree.

yangshijie 3 Jan 7, 2023
Comments
  • Implement (probably) faster and more correct LSB and MSB

    Implement (probably) faster and more correct LSB and MSB

    Since you seem to be interested in having all the performance tricks there are, I used one I know to implement MSB with fewer instructions (see this comparison: https://godbolt.org/z/oje47ns3b). In theory this should make it faster, though instruction count isn't necessarily an indicator of execution time. It also has the added bonus of making it correct on platforms where usize is not 64 bits.

    I also changed both methods to use usize, because casting to isize during bit fiddling just feels dirty.

    opened by FeldrinH 4
Releases(v1.0.0)
Owner
Bruno Rucy Carneiro Alves de Lima
🧙
Bruno Rucy Carneiro Alves de Lima
GitHub
Precio is a Rust library that implements the Precio protocol for computing private layered histograms and sums.

Overview of Precio Precio is a Rust implementation of the protocol described in eprint.iacr.org/2021/1490. The goal of the protocol is to enable an an

Microsoft 9 Aug 16, 2023
The Fast Vector Similarity Library is designed to provide efficient computation of various similarity measures between vectors.

Fast Vector Similarity Library Introduction The Fast Vector Similarity Library is designed to provide efficient computation of various similarity meas

Jeff Emanuel 243 Sep 6, 2023
🦀 Rust crate that allows creating weighted prefix trees that can be used in autocomplete

weighted_trie ?? Rust crate that allows creating weighted prefix trees that can be used in autocomplete Released API Docs Quickstart To use weigthed-t

Alexander Osipenko 8 Mar 1, 2023
Safe Rust bindings to the DynamoRIO dynamic binary instrumentation framework.

Introduction The dynamorio-rs crate provides safe Rust bindings to the DynamoRIO dynamic binary instrumentation framework, essentially allowing you to

S.J.R. van Schaik 17 Nov 21, 2022
Oxido is a dynamic interpreted programming language basing most of its syntax on Rust.

Oxido Table of Contents: Oxido Installation Uninstallation Usage Syntax Data types Variables Reassignments Printing If statements Loop statements Func

Oxido 6 Oct 6, 2022
A simple path traversal checker made with Rust. Useful for APIs that serve dynamic files.

Path trav A simple path traversal checker made with Rust. Useful for APIs that serve dynamic files. Note: this is a security tool. If you see somethin

Gátomo 3 Nov 21, 2022
Keep a Hetzner Cloud firewall up to date with your dynamic public IP address.

hcloud-firewall-controller hcloud-firewall-controller determines the current public IP and creates or updates a Hetzner Cloud firewall with this IP. S

Max Rosin 4 Feb 6, 2023
cargo-add command to make dependencies into dylibs

cargo add-dynamic This cargo command allows to wrap dependencies as dylibs. For why you might want this see Speeding up incremental Rust compilation w

Robert Krahn 62 Dec 27, 2022
Code to follow along the "Zero To Production" book on API development in Rust.

Zero To Production / Code (Chapter 10 - Part 1) Zero To Production In Rust is an opinionated introduction to backend development using Rust. This repo

Luca Palmieri 2.8k Dec 31, 2022
A set of Zero Knowledge modules, written in Rust and designed to be used in other system programming environments.

Zerokit A set of Zero Knowledge modules, written in Rust and designed to be used in other system programming environments. Initial scope Focus on RLN

vac 44 Dec 27, 2022