FilesExpand file tree

 master

/

Fenwick_Tree.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

30 lines (29 loc) · 763 Bytes

 master

/

Fenwick_Tree.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

30 lines (29 loc) · 763 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

/*

Task : Fenwick_Tree

Author : Phumipat C. [MAGCARI]

School : RYW

Language : C++

Explanation : https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/

Visualgo : https://visualgo.net/en/fenwicktree

Created : 03 May 2021 [12:04]

*/

#include<bits/stdc++.h>

#define all(x) begin(x),end(x)

#define sz(x) (int)(x).size()

using namespace std;

using LL = long long;

using PII = pair<int ,int >;

using PLL = pair<long long ,long long >;

const int dir4[2][4] = {{1,-1,0,0},{0,0,1,-1}};

const int dir8[2][8] = {{-1,-1,-1,0,1,1,1,0},{-1,0,1,1,-1,0,1,-1}};

const int N = 100000;

LL tree[N+10];

void upd(int idx,int v){

for(;idx<=N;idx+=idx&=idx)

tree[idx]+=v;

}

LL read(int idx,LL sum=0){

for(;idx;idx-=idx&-idx)

sum+=tree[idx];

return sum;

}