Skip to content

Instantly share code, notes, and snippets.

@dipta10

dipta10/Binary Indexed Tree | Fenwick Tree #RMQ.cpp

Last active June 20, 2023 10:21
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save dipta10/8bdc77376027ed3d5b81e90436a8d5bd to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save dipta10/8bdc77376027ed3d5b81e90436a8d5bd to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. dipta10 revised this gist Nov 29, 2018. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion Binary Indexed Tree | Fenwick Tree #RMQ.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -7,7 +7,7 @@
    * https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
    * https://www.youtube.com/playlist?list=PLDV1Zeh2NRsCvoyP-bztk6uXAYoyZg_U9
    * https://www.hackerearth.com/practice/notes/binary-indexed-tree-or-fenwick-tree/
    * Source Code:
    * Source Code: https://gist.github.com/dipta10/8bdc77376027ed3d5b81e90436a8d5bd
    */

    #include <bits/stdc++.h>
  2. dipta10 created this gist Nov 29, 2018.
    65 changes: 65 additions & 0 deletions Binary Indexed Tree | Fenwick Tree #RMQ.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,65 @@
    /*
    * Created by Dipta Das on 23-11-2018
    * Title: Binary Indexed Tree/Fenwich Tree
    * Editorial
    * https://www.topcoder.com/community/competitive-programming/tutorials/binary-indexed-trees/
    * http://www.shafaetsplanet.com/?p=1961&fbclid=IwAR23aI879JfPHbIaW3y93Du6Ql_68DCTxcUY6euLJUWsLvgtvj_-b2tKJCE
    * https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
    * https://www.youtube.com/playlist?list=PLDV1Zeh2NRsCvoyP-bztk6uXAYoyZg_U9
    * https://www.hackerearth.com/practice/notes/binary-indexed-tree-or-fenwick-tree/
    * Source Code:
    */

    #include <bits/stdc++.h>
    #include <stdio.h>
    #define fin freopen("input", "r", stdin)
    #define whatis(x) cerr << #x << ": " << x << endl;

    using namespace std;
    using ll = long long;

    #define mx 10000
    int ar[mx];
    int tree[mx];

    int read(int idx){
    int sum = 0;
    while (idx > 0){
    sum += tree[idx];
    idx -= (idx & -idx);
    }
    return sum;
    }

    void update(int idx, int val, int n){
    while (idx <= n){
    tree[idx] += val;
    idx += (idx & -idx);
    }
    }

    void print(int *ar, int n) {
    for (int i = 1; i <= n; ++i) {
    cout << ar[i] << " ";
    }
    puts("");
    }

    int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n; cin >> n;
    for (int i = 1; i <= n; ++i) { cin >> ar[i]; update(i, ar[i], n); }

    cout << "input array:\t";
    print(ar, n);
    cout << "\n";

    cout << "tree array:\t";
    print(tree, n);
    cout << "\n";


    return 0;
    }