Last active
June 20, 2023 10:21
-
-
Save dipta10/8bdc77376027ed3d5b81e90436a8d5bd to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| * 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: https://gist.github.com/dipta10/8bdc77376027ed3d5b81e90436a8d5bd | |
| */ | |
| #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; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment