# C++ Data Structure
## Prefix Sum
Practice Problems:
1. [CSES Static Range Sum Queries](https://cses.fi/problemset/task/1646)
```clike=
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string.h>
#include <climits>
using namespace std;
#define pb push_back
#define ll long long
const ll MAXN = 2e5 + 5;
ll N, Q;
ll arr[MAXN], sum[MAXN];
void build() {
sum[0] = arr[0];
for(int i = 1; i < N; i++) {
sum[i] = sum[i - 1] + arr[i];
}
}
ll query(int a, int b) {
return sum[b - 1] - sum[a - 2];
}
int main() {
while(cin >> N >> Q) {
for(int i = 0; i < N; i++) {
cin >> arr[i];
}
build();
for(int i = 0; i < Q; i++) {
int a, b; cin >> a >> b;
cout << query(a, b) << endl;
}
}
}
```
2. [CSES Forest Queries](https://cses.fi/problemset/task/1652/)
```clike!
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string.h>
#include <climits>
using namespace std;
#define pb push_back
#define ll long long
#define AC ios_base::sync_with_stdio(false);cin.tie(NULL)
const ll MAXN = 2e5 + 5;
ll N, Q;
string arr[1002];
ll sum[1002][1002];
void build() {
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++) {
if(arr[i][j - 1] == '*') {
sum[i][j] = sum[i][j - 1] + 1;
} else {
sum[i][j] = sum[i][j - 1];
}
}
}
}
ll query(int a, int b, int c, int d) {
int total = 0;
for(int i = b; i <= d; i++) {
total += sum[i][c] - sum[i][a - 1];
}
return total;
}
int main() {
AC;
while(cin >> N >> Q) {
for(int i = 1; i <= N; i++) {
cin >> arr[i];
}
memset(sum, 0, sizeof(sum));
build();
for(int i = 0; i < Q; i++) {
int a, b, c ,d; cin >> a >> b >> c >> d;
cout << query(b, a, d, c) << endl;
}
}
```
## BIT (Binary Index Tree)
### Binary
* (-) binary (2’s complement)
* change 1 to 0 and 0 to 1
* Add 1
* ex. 3 and -3
1. 3 binary: 0 0 0 0 0 0 1 1
2. 01 replacement: 1 1 1 1 1 1 0 0
3. Add 1
4. -3 binary: 1 1 1 1 1 1 0 1
### lowbit
* 3 = 0011, lowbit(3) = 0001
* 6 = 0110, lowbit(6) = 0010
* 8 = 1000, lowbit(8) = 1000
### Practice Problems
1. [CSES Dynamic Range Sum Queries](https://cses.fi/problemset/task/1648/)
```clike!
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string.h>
#include <climits>
using namespace std;
#define pb push_back
#define ll long long
#define AC ios_base::sync_with_stdio(false);cin.tie(NULL)
const ll MAXN = 2e5 + 5;
ll N, Q;
ll arr[MAXN], bit[MAXN];
ll lowbit(ll x) {
return x & (-x);
}
ll query (ll a, ll b) {
ll suma = 0, sumb = 0, num = a;
ll low = lowbit(a);
while(low > 0) {
suma += bit[a];
a -= low;
low = lowbit(a);
}
low = lowbit(b);
while(low > 0) {
sumb += bit[b];
b -= low;
low = lowbit(b);
}
return sumb - suma + arr[num];
}
void modify(ll k, ll u) {
ll num = u - arr[k];
arr[k] = u;
while(k <= N) {
bit[k] += num;
k += lowbit(k);
}
}
int main() {
AC;
while(cin >> N >> Q) {
arr[0] = 0;
bit[0] = 0;
for(ll i = 1; i <= N; i++) {
arr[i] = 0;
int num; cin >> num;
modify(i, num);
}
for(ll i = 0; i < Q; i++) {
ll a, b, c; cin >> a >> b >> c;
if(a == 1) {
modify(b, c);
} else {
cout << query(b, c) << endl;
}
}
}
}
```
## Segment Tree
### Practice Problems
● 無修改
○ CSES - Static Range Minimum Queries
○ CSES - Range Xor Queries
● 單點修改
○ CSES - Dynamic Range Sum Queries
○ CSES - Dynamic Range Minimum Queries
○ LeetCode 307. Range Sum Query - Mutable
○ CSES - Hotel Queries (遞迴時二分搜)
○ CSES - List Removals (遞迴時二分搜)
○ CSES - Salary Queries
● 應用題
○ zerojudge c265: 數學遊戲
○ CSES - Josephus Problem II