C++ Data Structure

Prefix Sum

Practice Problems:

1. CSES Static Range Sum Queries

#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

#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

#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