Add portable formulas for fenwick calculations

JJCUBER · web-flow · commit b1e38373d20f · 2024-06-26T21:10:10.000-04:00
Alongside the equations provided to calculate g(i) and h(i), I provided some alternative ones which are more portable.

(Prior to C++20, it wasn't guaranteed that signed integers would be represented as two's complement, and the formulas I added do not rely on this, unlike the formulas previously mentioned in this Fenwick tree article.  One exception would be when i = 0, but 0 &amp; x, where x is any integer, is always 0.)
diff --git a/src/data_structures/fenwick.md b/src/data_structures/fenwick.md
@@ -300,6 +300,18 @@ $$h(i) = i + (i ~\&~ (-i)).$$
 
 As you can see, the main benefit of this approach is that the binary operations complement each other very nicely.
 
+**Note**: for improved portability, the extraction of the last set bit can alternatively be computed as  $i - (i ~\&~ (i-1))$.  Accordingly:
+
+$$g(i) = i ~\&~ (i-1)$$
+
+and
+
+$$h(i) = 2i - (i ~\&~ (i-1)).$$
+
+This also allows the code for $g(i)$ to be succinctly written as `i &= i - 1`.
+
+An example of this lack of portability is any version of C++ prior to C++20.  Before [C++20](https://en.cppreference.com/w/cpp/20), it was not guaranteed for signed integers to be implemented as [two's complement](https://en.wikipedia.org/wiki/Two%27s_complement), so the use of negative numbers ($-i$) alongside bitwise-and ($~\&~$) could ([theoretically](https://en.cppreference.com/w/cpp/language/types#Range_of_values)) lead to unexpected results.
+
 The following implementation can be used like the other implementations, however it uses one-based indexing internally.
 
 ```{.cpp file=fenwick_sum_onebased}
@@ -335,6 +347,21 @@ struct FenwickTreeOneBasedIndexing {
     }
 };
 ```
+An equivalent implementation which utilizes the more portable formulas would have the following changes:
+
+```cpp
+    int sum(int idx) {
+        int ret = 0;
+        for (++idx; idx > 0; idx &= idx - 1)
+            ret += bit[idx];
+        return ret;
+    }
+
+    void add(int idx, int delta) {
+        for (++idx; idx < n; idx += idx - (idx & (idx - 1))
+            bit[idx] += delta;
+    }
+```
 
 ## Range operations
 
