The Fenwick Tree, also called Binary Indexed Tree, is a data structure used to update elements and evaluate range queries in arrays. It differs from other similar data structures by using a method to arrange binary numbers in two dimensions.

Its straightforward implementation hides beautiful properties that explain how and why it works. This article tries to visually explain what a Fenwick Tree is, why it has to be 1-indexed, how to walk on the tree using the least significant bit, and, most importantly, how someone could come up with the idea of this structure, whose properties seem like magic.

The range sum query problem

A treap is a binary tree that maintains simultaneously the property of binary search tree (BST) and heap.

This is the first article of a series that aims to explain what a treap is, how to implement it and when to use it. It’s an advanced data structure with some really beautiful properties.

If you have any suggestions or questions, please, comment here or tell me on Twitter.

The treap data structure

Formally, a treap (tree + heap) is a binary tree whose nodes contain two values, a key and a priority, such that the key keeps the BST property and the priority is…

This article is my interpretation of Tanuj Khatta’s awesome tutorial. I’ll change some things in my explanation, but he did an incredible job building the structure of his text and I’ll try to follow it.

The centroid decomposition is a very simple idea that is able to solve some really scary problems. In fact, you only need to know depth first search to understand it.

I’ll split this article into three pieces. First, we’ll see an example of a problem that the centroid decomposition tries to solve. Then, we’ll define what a centroid and a centroid decomposition are. …

Publicado originalmente para o Projeto de Extensão Segurança em Sistemas Eletrônicos de Votação, na Universidade Federal do Rio de Janiro.

Agradecimentos ao Prof. Luis Menasché pela revisão do texto.

Para o leitor mais jovem, é difícil não associar eleição às tecnologias que hoje estão presentes. Bem verdade que estamos longe da perfeição, se é que ela existe, mas o que podemos aprender olhando para os sistemas muito mais primitivos do que o nosso?

Compreender os diferentes métodos surgidos ao longo da história da Democracia nos ajuda a discordar/concordar não apenas do que é feito hoje, mas também de novas ideias…

Igor Carpanese

I created this account to be a place where I can share insights and drafts about Computer Science.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store