cp-algorithms
diff --git a/‎README.md
Lines changed: 1 addition & 0 deletions b/‎README.md
Lines changed: 1 addition & 0 deletions
diff --git a/‎mkdocs.yml
Lines changed: 1 addition & 1 deletion b/‎mkdocs.yml
Lines changed: 1 addition & 1 deletion
diff --git a/‎src/algebra/bit-manipulation.md
Lines changed: 38 additions & 0 deletions b/‎src/algebra/bit-manipulation.md
Lines changed: 38 additions & 0 deletions
diff --git a/‎src/algebra/euclid-algorithm.md
Lines changed: 1 addition & 0 deletions b/‎src/algebra/euclid-algorithm.md
Lines changed: 1 addition & 0 deletions
diff --git a/‎src/algebra/polynomial.md
Lines changed: 1 addition & 1 deletion b/‎src/algebra/polynomial.md
Lines changed: 1 addition & 1 deletion
diff --git a/‎src/combinatorics/bracket_sequences.md
Lines changed: 10 additions & 11 deletions b/‎src/combinatorics/bracket_sequences.md
Lines changed: 10 additions & 11 deletions
diff --git a/‎src/data_structures/disjoint_set_union.md
Lines changed: 1 addition & 1 deletion b/‎src/data_structures/disjoint_set_union.md
Lines changed: 1 addition & 1 deletion
diff --git a/‎src/data_structures/fenwick.md
Lines changed: 37 additions & 32 deletions b/‎src/data_structures/fenwick.md
Lines changed: 37 additions & 32 deletions
@@ -26,6 +26,7 @@ Compiled pages are published at [https://cp-algorithms.com/](https://cp-algorith
 
 ### New articles
 
+- (8 June 2024) [Knapsack Problem](https://cp-algorithms.com/dynamic_programming/knapsack.html)
 - (28 January 2024) [Introduction to Dynamic Programming](https://cp-algorithms.com/dynamic_programming/intro-to-dp.html)
 - (8 December 2023) [Hungarian Algorithm](https://cp-algorithms.com/graph/hungarian-algorithm.html)
 - (10 September 2023) [Tortoise and Hare Algorithm](https://cp-algorithms.com/others/tortoise_and_hare.html)
 
@@ -32,7 +32,7 @@ edit_uri: edit/master/src/
 copyright: Text is available under the <a href="https://github.com/cp-algorithms/cp-algorithms/blob/master/LICENSE">Creative Commons Attribution Share Alike 4.0 International</a> License<br/>Copyright &copy; 2014 - 2024 by <a href="https://github.com/cp-algorithms/cp-algorithms/graphs/contributors">cp-algorithms contributors</a>
 extra_javascript:
   - javascript/config.js
-  - https://polyfill.io/v3/polyfill.min.js?features=es6
+  - https://cdnjs.cloudflare.com/polyfill/v3/polyfill.min.js?features=es6
   - https://unpkg.com/mathjax@3/es5/tex-mml-chtml.js
 extra_css:
   - stylesheets/extra.css
 
@@ -186,6 +186,44 @@ int countSetBits(int n)
 }
 ```
 
+### Count set bits upto $n$
+To count the number of set bits of all numbers upto the number $n$ (inclusive), we can run the Brian Kernighan's algorithm on all numbers upto $n$. But this will result in a "Time Limit Exceeded" in contest submissions. 
+
+We can use the fact that for numbers upto $2^x$ (i.e. from $1$ to $2^x - 1$) there are $x \cdot 2^{x-1}$ set bits. This can be visualised as follows.
+```
+0 ->   0 0 0 0
+1 ->   0 0 0 1
+2 ->   0 0 1 0
+3 ->   0 0 1 1
+4 ->   0 1 0 0
+5 ->   0 1 0 1
+6 ->   0 1 1 0
+7 ->   0 1 1 1
+8 ->   1 0 0 0
+```
+
+We can see that the all the columns except the leftmost have $4$ (i.e. $2^2$) set bits each, i.e. upto the number $2^3 - 1$, the number of set bits is $3 \cdot 2^{3-1}$.
+
+With the new knowledge in hand we can come up with the following algorithm:
+
+- Find the highest power of $2$ that is lesser than or equal to the given number. Let this number be $x$.
+- Calculate the number of set bits from $1$ to $2^x - 1$ by using the formua $x \cdot 2^{x-1}$.
+- Count the no. of set bits in the most significant bit from $2^x$ to $n$ and add it.
+- Subtract $2^x$ from $n$ and repeat the above steps using the new $n$.
+
+```cpp
+int countSetBits(int n) {
+        int count = 0;
+        while (n > 0) {
+            int x = std::bit_width(n) - 1;
+            count += x << (x - 1);
+            n -= 1 << x;
+            count += n + 1;
+        }
+        return count;
+}
+```
+
 ### Additional tricks
 
 - $n ~\&~ (n + 1)$ clears all trailing ones: $0011~0111_2 \rightarrow 0011~0000_2$.
 
@@ -126,3 +126,4 @@ E.g. C++17 has such a function `std::gcd` in the `numeric` header.
 ## Practice Problems
 
 - [CSAcademy - Greatest Common Divisor](https://csacademy.com/contest/archive/task/gcd/)
+- [Codeforces 1916B - Two Divisors](https://codeforces.com/contest/1916/problem/B)
@@ -140,7 +140,7 @@ Polynomial long division is useful because of its many important properties:
 Note that long division can't be properly defined for formal power series. Instead, for any $A(x)$ such that $a_0 \neq 0$, it is possible to define an inverse formal power series $A^{-1}(x)$, such that $A(x) A^{-1}(x) = 1$. This fact, in turn, can be used to compute the result of long division for polynomials.
 
 ## Basic implementation
-[Here](https://cp-algorithms.github.io/cp-algorithms-aux/cp-algo/algebra/poly.hpp) you can find the basic implementation of polynomial algebra.
+[Here](https://cp-algorithms.github.io/cp-algorithms-aux/cp-algo/math/poly.hpp) you can find the basic implementation of polynomial algebra.
 
 It supports all trivial operations and some other useful methods. The main class is `poly<T>` for polynomials with coefficients of type `T`.
 
 
@@ -32,7 +32,7 @@ We iterate over all character of the string, if the current bracket character is
 If at any time the variable $\text{depth}$ gets negative, or at the end it is different from $0$, then the string is not a balanced sequence.
 Otherwise it is.
 
-If there are several bracket types involved, then the algorithm needs to be changes.
+If there are several bracket types involved, then the algorithm needs to be changed.
 Instead of a counter $\text{depth}$ we create a stack, in which we will store all opening brackets that we meet.
 If the current bracket character is an opening one, we put it onto the stack.
 If it is a closing one, then we check if the stack is non-empty, and if the top element of the stack is of the same type as the current closing bracket.
@@ -49,7 +49,7 @@ The number of balanced bracket sequences of length $2n$ ($n$ pairs of brackets)
 
 $$\frac{1}{n+1} \binom{2n}{n}$$
 
-If we allow $k$ types of brackets, then each pair be of any of the $k$ types (independently of the others), thus the number of balanced bracket sequences is:
+If we allow $k$ types of brackets, then each pair can be of any of the $k$ types (independently of the others), thus the number of balanced bracket sequences is:
 
 $$\frac{1}{n+1} \binom{2n}{n} k^n$$
 
@@ -82,7 +82,7 @@ When we meet an opening brackets, we will decrement $\text{depth}$, and when we
 If we are at some point meet an opening bracket, and the balance after processing this symbol is positive, then we have found the rightmost position that we can change.
 We change the symbol, compute the number of opening and closing brackets that we have to add to the right side, and arrange them in the lexicographically minimal way.
 
-If we find do suitable position, then this sequence is already the maximal possible one, and there is no answer.
+If we don't find a suitable position, then this sequence is already the maximal possible one, and there is no answer.
 
 ```{.cpp file=next_balanced_brackets_sequence}
 bool next_balanced_sequence(string & s) {
@@ -117,7 +117,7 @@ To generate then, we can start with the lexicographically smallest sequence $((\
 
 However, if the length of the sequence is not very long (e.g. $n$ smaller than $12$), then we can also generate all permutations conveniently with the C++ STL function `next_permutation`, and check each one for balanceness.
 
-Also they can be generate using the ideas we used for counting all sequences with dynamic programming.
+Also they can be generated using the ideas we used for counting all sequences with dynamic programming.
 We will discuss the ideas in the next two sections.
 
 ## Sequence index
@@ -142,19 +142,19 @@ Thus we can compute this array in $O(n^2)$.
 Now let us generate the index for a given sequence.
 
 First let there be only one type of brackets.
-We will us the counter $\text{depth}$ which tells us how nested we currently are, and iterate over the characters of the sequence.
+We will use the counter $\text{depth}$ which tells us how nested we currently are, and iterate over the characters of the sequence.
 If the current character $s[i]$ is equal to $($, then we increment $\text{depth}$.
 If the current character $s[i]$ is equal to $)$, then we must add $d[2n-i-1][\text{depth}+1]$ to the answer, taking all possible endings starting with a $($ into account (which are lexicographically smaller sequences), and then decrement $\text{depth}$.
 
 New let there be $k$ different bracket types.
 
-Thus, when we look at the current character $s[i]$ before recomputing $\text{depth}$, we have to go through all bracket types that are smaller than the current character, and try to put this bracket into the current position (obtaining a new balance $\text{ndepth} = \text{depth} \pm 1$), and add the number of ways to finish the sequence (length $2n-i-1$, balance $ndepth$) to the answer:
+Thus, when we look at the current character $s[i]$ before recomputing $\text{depth}$, we have to go through all bracket types that are smaller than the current character, and try to place this bracket into the current position (obtaining a new balance $\text{ndepth} = \text{depth} \pm 1$), and add the number of ways to finish the sequence (length $2n-i-1$, balance $ndepth$) to the answer:
 
 $$d[2n - i - 1][\text{ndepth}] \cdot k^{\frac{2n - i - 1 - ndepth}{2}}$$
 
 This formula can be derived as follows:
 First we "forget" that there are multiple bracket types, and just take the answer $d[2n - i - 1][\text{ndepth}]$.
-Now we consider how the answer will change is we have $k$ types of brackets.
+Now we consider how the answer will change if we have $k$ types of brackets.
 We have $2n - i - 1$ undefined positions, of which $\text{ndepth}$ are already predetermined because of the opening brackets.
 But all the other brackets ($(2n - i - 1 - \text{ndepth})/2$ pairs) can be of any type, therefore we multiply the number by such a power of $k$.
 
@@ -169,10 +169,9 @@ First, we start with only one bracket type.
 
 We will iterate over the characters in the string we want to generate.
 As in the previous problem we store a counter $\text{depth}$, the current nesting depth.
-In each position we have to decide if we use an opening of a closing bracket.
-To have to put an opening bracket character, it $d[2n - i - 1][\text{depth}+1] \ge k$.
-We increment the counter $\text{depth}$, and move on to the next character.
-Otherwise we decrement $k$ by $d[2n - i - 1][\text{depth}+1]$, put a closing bracket and move on.
+At each position, we have to decide whether to place an opening or a closing bracket. To place an opening bracket, $d[2n - i - 1][\text{depth}+1] \ge k$ must be true.
+If so, we increment the counter $\text{depth}$, and move on to the next character.
+Otherwise, we decrement $k$ by $d[2n - i - 1][\text{depth}+1]$, place a closing bracket, and move on.
 
 ```{.cpp file=kth_balances_bracket}
 string kth_balanced(int n, int k) {
 
@@ -375,7 +375,7 @@ If we add an edge $(a, b)$ that connects two connected components into one, then
 
 Let's derive a formula, which computes the parity issued to the leader of the set that will get attached to another set.
 Let $x$ be the parity of the path length from vertex $a$ up to its leader $A$, and $y$ as the parity of the path length from vertex $b$ up to its leader $B$, and $t$ the desired parity that we have to assign to $B$ after the merge.
-The path contains the of the three parts:
+The path consists of the three parts:
 from $B$ to $b$, from $b$ to $a$, which is connected by one edge and therefore has parity $1$, and from $a$ to $A$.
 Therefore we receive the formula ($\oplus$ denotes the XOR operation):
 
 
@@ -6,44 +6,48 @@ e_maxx_link: fenwick_tree
 
 # Fenwick Tree
 
-Let, $f$ be some group operation (binary associative function over a set with identity element and inverse elements) and $A$ be an array of integers of length $N$.
+Let $f$ be some group operation (a binary associative function over a set with an identity element and inverse elements) and $A$ be an array of integers of length $N$.
+Denote $f$'s infix notation as $*$; that is, $f(x,y) = x*y$ for arbitrary integers $x,y$.
+(Since this is associative, we will omit parentheses for order of application of $f$ when using infix notation.)
 
-Fenwick tree is a data structure which:
+The Fenwick tree is a data structure which:
 
-* calculates the value of function $f$ in the given range $[l, r]$ (i.e. $f(A_l, A_{l+1}, \dots, A_r)$) in $O(\log N)$ time;
-* updates the value of an element of $A$ in $O(\log N)$ time;
-* requires $O(N)$ memory, or in other words, exactly the same memory required for $A$;
-* is easy to use and code, especially, in the case of multidimensional arrays.
+* calculates the value of function $f$ in the given range $[l, r]$ (i.e. $A_l * A_{l+1} * \dots * A_r$) in $O(\log N)$ time
+* updates the value of an element of $A$ in $O(\log N)$ time
+* requires $O(N)$ memory (the same amount required for $A$)
+* is easy to use and code, especially in the case of multidimensional arrays
 
-The most common application of Fenwick tree is _calculating the sum of a range_ (i.e. using addition over the set of integers $\mathbb{Z}$: $f(A_1, A_2, \dots, A_k) = A_1 + A_2 + \dots + A_k$).
+The most common application of a Fenwick tree is _calculating the sum of a range_.
+For example, using addition over the set of integers as the group operation, i.e. $f(x,y) = x + y$: the binary operation, $*$, is $+$ in this case, so $A_l * A_{l+1} * \dots * A_r = A_l + A_{l+1} + \dots + A_{r}$.
 
-Fenwick tree is also called **Binary Indexed Tree**, or just **BIT** abbreviated.
-
-Fenwick tree was first described in a paper titled "A new data structure for cumulative frequency tables" (Peter M. Fenwick, 1994).
+The Fenwick tree is also called a **Binary Indexed Tree** (BIT).
+It was first described in a paper titled "A new data structure for cumulative frequency tables" (Peter M. Fenwick, 1994).
 
 ## Description
 
 ### Overview
 
-For the sake of simplicity, we will assume that function $f$ is just a *sum function*.
+For the sake of simplicity, we will assume that function $f$ is defined as $f(x,y) = x + y$ over the integers.
 
-Given an array of integers $A[0 \dots N-1]$.
-A Fenwick tree is just an array $T[0 \dots N-1]$, where each of its elements is equal to the sum of elements of $A$ in some range $[g(i), i]$:
+Suppose we are given an array of integers, $A[0 \dots N-1]$.
+(Note that we are using zero-based indexing.)
+A Fenwick tree is just an array, $T[0 \dots N-1]$, where each element is equal to the sum of elements of $A$ in some range, $[g(i), i]$:
 
-$$T_i = \sum_{j = g(i)}^{i}{A_j},$$
+$$T_i = \sum_{j = g(i)}^{i}{A_j}$$
 
 where $g$ is some function that satisfies $0 \le g(i) \le i$.
-We will define the function in the next few paragraphs.
+We will define $g$ in the next few paragraphs.
 
-The data structure is called tree, because there is a nice representation of the data structure as tree, although we don't need to model an actual tree with nodes and edges.
-We will only need to maintain the array $T$ to handle all queries.
+The data structure is called a tree because there is a nice representation of it in the form of a tree, although we don't need to model an actual tree with nodes and edges.
+We only need to maintain the array $T$ to handle all queries.
 
 **Note:** The Fenwick tree presented here uses zero-based indexing.
-Many people will actually use a version of the Fenwick tree that uses one-based indexing.
-Therefore you will also find an alternative implementation using one-based indexing in the implementation section.
+Many people use a version of the Fenwick tree that uses one-based indexing.
+As such, you will also find an alternative implementation which uses one-based indexing in the implementation section.
 Both versions are equivalent in terms of time and memory complexity.
 
-Now we can write some pseudo-code for the two operations mentioned above - get the sum of elements of $A$ in the range $[0, r]$ and update (increase) some element $A_i$:
+Now we can write some pseudo-code for the two operations mentioned above.
+Below, we get the sum of elements of $A$ in the range $[0, r]$ and update (increase) some element $A_i$:
 
 ```python
 def sum(int r):
@@ -60,20 +64,21 @@ def increase(int i, int delta):
 
 The function `sum` works as follows:
 
-1. first, it adds the sum of the range $[g(r), r]$ (i.e. $T[r]$) to the `result`
-2. then, it "jumps" to the range $[g(g(r)-1), g(r)-1]$, and adds this range's sum to the `result`
-3. and so on, until it "jumps" from $[0, g(g( \dots g(r)-1 \dots -1)-1)]$ to $[g(-1), -1]$; that is where the `sum` function stops jumping.
+1. First, it adds the sum of the range $[g(r), r]$ (i.e. $T[r]$) to the `result`.
+2. Then, it "jumps" to the range $[g(g(r)-1), g(r)-1]$ and adds this range's sum to the `result`.
+3. This continues until it "jumps" from $[0, g(g( \dots g(r)-1 \dots -1)-1)]$ to $[g(-1), -1]$; this is where the `sum` function stops jumping.
 
-The function `increase` works with the same analogy, but "jumps" in the direction of increasing indices:
+The function `increase` works with the same analogy, but it "jumps" in the direction of increasing indices:
 
-1. sums of the ranges $[g(j), j]$ that satisfy the condition $g(j) \le i \le j$ are increased by `delta` , that is `t[j] += delta`. Therefore we updated all elements in $T$ that correspond to ranges in which $A_i$ lies.
+1. The sum for each range of the form $[g(j), j]$ which satisfies the condition $g(j) \le i \le j$ is increased by `delta`; that is, `t[j] += delta`.
+Therefore, it updates all elements in $T$ that correspond to ranges in which $A_i$ lies.
 
-It is obvious that the complexity of both `sum` and `increase` depend on the function $g$.
-There are lots of ways to choose the function $g$, as long as $0 \le g(i) \le i$ for all $i$.
-For instance the function $g(i) = i$ works, which results just in $T = A$, and therefore summation queries are slow.
-We can also take the function $g(i) = 0$.
-This will correspond to prefix sum arrays, which means that finding the sum of the range $[0, i]$ will only take constant time, but updates are slow.
-The clever part of the Fenwick algorithm is, that there it uses a special definition of the function $g$ that can handle both operations in $O(\log N)$ time.
+The complexity of both `sum` and `increase` depend on the function $g$.
+There are many ways to choose the function $g$ such that $0 \le g(i) \le i$ for all $i$.
+For instance, the function $g(i) = i$ works, which yields $T = A$ (in which case, the summation queries are slow).
+We could also take the function $g(i) = 0$.
+This would correspond to prefix sum arrays (in which case, finding the sum of the range $[0, i]$ will only take constant time; however, updates are slow).
+The clever part of the algorithm for Fenwick trees is how it uses a special definition of the function $g$ which can handle both operations in $O(\log N)$ time.
 
 ### Definition of $g(i)$ { data-toc-label='Definition of <script type="math/tex">g(i)</script>' }
 
@@ -380,7 +385,7 @@ int point_query(int idx) {
 
 Note: of course it is also possible to increase a single point $A[i]$ with `range_add(i, i, val)`.
 
-### 3. Range Updates and Range Queries
+### 3. Range Update and Range Query
 
 To support both range updates and range queries we will use two BITs namely $B_1[]$ and $B_2[]$, initialized with zeros.
Original file line number	Diff line number	Diff line change
@@ -126,3 +126,4 @@ E.g. C++17 has such a function `std::gcd` in the `numeric` header.
`126`	`126`	`## Practice Problems`
`127`	`127`
`128`	`128`	`- [CSAcademy - Greatest Common Divisor](https://csacademy.com/contest/archive/task/gcd/)`
	`129`	`+- [Codeforces 1916B - Two Divisors](https://codeforces.com/contest/1916/problem/B)`