Header File Templates

C++ Template

#include <bits/stdc++.h>

#define fi first
#define endl '\n'
#define se second
#define lowbit(x) ((x)&(-(x)))
#define all(x) begin(x), end(x)

#define lp(i, j, k) for(int i = int(j); i <= int(k); i++)
#define rlp(i, j, k) for(int i = int(j); i >= int(k); i++)

#define IO std::ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

using namespace std;
using ll = long long;
using pii = std::pair<int, int>;

template <class T> inline void chkmax(T& x, T y) { if (x < y) x = y; }
template <class T> inline void chkmin(T& x, T y) { if (x > y) x = y; }

const int MAXN = 1e6 + 10;
const int MAXT = 2e3 + 10;
const int INF = 0x3f3f3f3f;

int dx[8] = {0, 1, 0, -1, 1, -1, -1, 1};
int dy[8] = {1, 0, -1, 0, 1, -1, 1, -1};

int arr[MAXN], brr[MAXN], frr[MAXN];
int dp[MAXT][MAXT];
int grid[MAXT][MAXT];

int n, m;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 998244353;

void solve() {
    // Implementation goes here
}

int main() {
    IO
    int test_cases = 1;
    // cin >> test_cases;
    while (test_cases--) solve();
    return 0;
}

Python I/O Snippets

# Read multiple integers from single line
a, b, c = (int(x) for x in input().split())
a, b, c = map(int, input().split())

# Read array of integers
nums = [int(x) for x in input().split()]

# Read multiple values
n, m, k = list(map(int, input().split()))
arr = list(map(int, input().split()))

# Factorial
import math
result = math.factorial(3)

Divide and Conquer

Geometric Series Sum

Computing the sum of geometric series: (1 + p + p^2 + \cdots + p^{k-1})

Even k:

[ \sum_{i=0}^{k-1} p^i = \sum_{i=0}^{k/2-1} p^i + \sum_{i=k/2}^{k-1} p^i = (1 + p^{k/2}) \cdot \sum_{i=0}^{k/2-1} p^i ]

Odd k: Convert to (k-1) even case: (p^{k-1} + sum(p, k-1)))

Time Complexity: O(log k)

ll power_mod(ll base, ll exp) {
    ll result = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) result = result * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return result;
}

ll geometric_sum(ll p, ll k) {
    if (k == 0) return 1;
    if (k & 1) {
        return (power_mod(p, k - 1) + geometric_sum(p, k - 1)) % MOD;
    }
    ll half = geometric_sum(p, k / 2);
    return ((1 + power_mod(p, k / 2)) % MOD * half) % MOD;
}

Data Structures

Segment Tree

Basic Implementation with Lazy Propagation

#include <bits/stdc++.h>

#define lp(i, j, k) for(int i = int(j); i <= int(k); i++)
#define IO std::ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

using namespace std;
using ll = long long;

const int MAXN = 1e6 + 10;
const int MOD = 998244353;

struct Node {
    ll left, right;
    ll sum;
    ll lazy;
} tree[MAXN << 2];

int arr[MAXN];
int n, q;

inline int left_child(int idx) { return idx << 1; }
inline int right_child(int idx) { return idx << 1 | 1; }

void pull(int idx) {
    tree[idx].sum = tree[left_child(idx)].sum + tree[right_child(idx)].sum;
}

void push(int idx) {
    if (tree[idx].lazy != 0) {
        ll tag = tree[idx].lazy;
        tree[left_child(idx)].lazy += tag;
        tree[right_child(idx)].lazy += tag;
        
        ll left_len = tree[left_child(idx)].right - tree[left_child(idx)].left + 1;
        ll right_len = tree[right_child(idx)].right - tree[right_child(idx)].left + 1;
        
        tree[left_child(idx)].sum += left_len * tag;
        tree[right_child(idx)].sum += right_len * tag;
        tree[idx].lazy = 0;
    }
}

void build(int idx, int l, int r) {
    tree[idx].left = l;
    tree[idx].right = r;
    tree[idx].lazy = 0;
    
    if (l == r) {
        tree[idx].sum = arr[l];
    } else {
        int mid = (l + r) >> 1;
        build(left_child(idx), l, mid);
        build(right_child(idx), mid + 1, r);
        pull(idx);
    }
}

void range_add(int idx, int l, int r, int val) {
    if (tree[idx].left >= l && tree[idx].right <= r) {
        tree[idx].lazy += val;
        ll len = tree[idx].right - tree[idx].left + 1;
        tree[idx].sum += len * val;
    } else {
        push(idx);
        int mid = (tree[idx].left + tree[idx].right) >> 1;
        if (l <= mid) range_add(left_child(idx), l, r, val);
        if (r > mid) range_add(right_child(idx), l, r, val);
        pull(idx);
    }
}

ll range_sum(int idx, int l, int r) {
    if (tree[idx].left >= l && tree[idx].right <= r) {
        return tree[idx].sum;
    }
    push(idx);
    ll ans = 0;
    int mid = (tree[idx].left + tree[idx].right) >> 1;
    if (l <= mid) ans += range_sum(left_child(idx), l, r);
    if (r > mid) ans += range_sum(right_child(idx), l, r);
    return ans;
}

void solve() {
    cin >> n >> q;
    lp(i, 1, n) cin >> arr[i];
    build(1, 1, n);

    while (q--) {
        int operation, x, y;
        cin >> operation >> x >> y;
        if (operation == 2) {
            cout << range_sum(1, x, y) << '\n';
        } else {
            int val;
            cin >> val;
            range_add(1, x, y, val);
        }
    }
}

int main() {
    IO
    solve();
    return 0;
}

This segment tree supports:

• Point update: Add value to a range
• Range query: Sum over a range
• Lazy propagation: Efficient range updates in O(log n)