From 0ab75cddde1c959fe434c6554f1d3e1ed2719780 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sun, 2 Oct 2016 18:49:19 +0200 Subject: Optical improvements of the datastructures section. --- datastructures/fenwickTree.cpp | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'datastructures/fenwickTree.cpp') diff --git a/datastructures/fenwickTree.cpp b/datastructures/fenwickTree.cpp index cd30329..86b1138 100644 --- a/datastructures/fenwickTree.cpp +++ b/datastructures/fenwickTree.cpp @@ -1,19 +1,19 @@ -vector FT; //Fenwick-Tree +vector FT; // Fenwick-Tree int n; -//Adds val to index i. Time Complexity O(log(n)) +// Addiert val zum Element an Index i. O(log(n)). void updateFT(int i, int val) { i++; while(i <= n) { FT[i] += val; i += (i & (-i)); } } -//Build an Fenwick-Tree over an array a. Time Complexity: O(n*log(n)) +// Baut Baum auf. O(n*log(n)). void buildFenwickTree(vector& a) { n = a.size(); FT.assign(n+1,0); for(int i = 0; i < n; i++) updateFT(i,a[i]); } -//Prefix-Sum of intervall [0..i]. Time Complexity: O(log(n)) +// Präfix-Summe über das Intervall [0..i]. O(log(n)). int prefix_sum(int i) { int sum = 0; i++; while(i > 0) { sum += FT[i]; i -= (i & (-i)); } -- cgit v1.2.3