樹狀陣列與線段樹

樹狀陣列

適用問題

• 某個位置上的數加上一個數
• 求某一個前綴和

c[x] = (x - lowbit(x), x] = (x - 2^k, x]
//c[x]的值為這個左開右閉區間的元素和, k為x的二進制表示中末尾0的個數, 即c[x]在樹狀陣列中的層數

常用操作及其相應函式

1. 某個位置上的數加上一個數

void add(int x, int v) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}

2. 求某一個前綴和

int query(int x) {
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) res += tr[i];
    return res;
}

1264. 動態求連續區間和

給定 n 個陣列成的一個數列，規定有兩種操作，一是修改某個元素，二是求子數列 [a,b][a,b] 的連續和，

輸入格式：

第一行包含兩個整數 n 和 m，分別表示數的個數和操作次數，

第二行包含 n 個整數，表示完整數列，

接下來 m 行，每行包含三個整數 k,a,b（ k=0，表示求子數列[a,b][a,b]的和；k=1，表示第 a 個數加 b），

數列從 1 開始計數，

輸出格式：

輸出若干行數字，表示 k=0 時，對應的子數列 [a,b][a,b] 的連續和，

資料范圍：

1≤n≤100000,

1≤m≤100000,

1≤a≤b≤n

輸入樣例：

10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8

輸出樣例：

11
30
35

代碼：

#include <iostream>

using namespace std;
int n, m;
const int N = 100010;
int a[N], tr[N];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int v) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}

int query(int x) {
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) res += tr[i];
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) add(i, a[i]);
    int c, x, y;
    for (int i = 0; i < m; ++i) {
        cin >> c >> x >> y;
        if (c) add(x, y);
        else cout << query(y) - query(x - 1) << endl;
    }
    return 0;
}

線段樹

const int N = 100010;
int w[N];
struct Node {
    int l, r;
    int sum;
} tr[N * 4];

常用操作

1. 單點修改
2. 區間查詢

常用函式

1. 用子節點資訊更新當前節點資訊

void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

2. 在一段區間上初始化線段樹

void build(int u, int l, int r) {
   if (l == r)tr[u] = {l, r, w[r]};
   else {
       tr[u] = {l, r};
       int mid = (l + r) >> 1;
       build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
       pushup(u);
   }
}

3. 修改

void modify(int u, int x, int v) {
    if (tr[u].l == tr[u].r)tr[u].sum += v;
    else {
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (x <= mid)modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

4. 查詢

int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r)return tr[u].sum;
    int mid = (tr[u].l + tr[u].r) >> 1;
    int sum = 0;
    if (l <= mid)sum += query(u << 1, l, r);
    if (r > mid)sum += query(u << 1 | 1, l, r);
    return sum;
}

1270. 數列區間最大值

輸入一串數字，給你 M 個詢問，每次詢問就給你兩個數字 X,Y，要求你說出 X 到 Y 這段區間內的最大數，

輸入格式：

第一行兩個整數 N,M 表示數字的個數和要詢問的次數；

接下來一行為 N 個數；

接下來 M 行，每行都有兩個整數 X,Y，

輸出格式：

輸出共 M 行，每行輸出一個數，

資料范圍：

1≤N≤105,

1≤M≤106,

1≤X≤Y≤N,

數列中的數字均不超過 2³¹?1

輸入樣例：

10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8

輸出樣例：

5
8

代碼：

#include<iostream>
#include<cstdio>

using namespace std;
int n, m;
const int N = 100010;
int w[N];
struct Node {
    int l, r;
    int maxv;
} tr[N * 4];

void pushup(int u) {
    tr[u].maxv = max(tr[u << 1].maxv, tr[u << 1 | 1].maxv);
}

void build(int u, int l, int r) {
    if (l == r)tr[u] = {l, r, w[r]};
    else {
        tr[u] = {l, r};
        int mid = (l + r) >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r)return tr[u].maxv;
    int mid = (tr[u].l + tr[u].r) >> 1;
    int mmax = 0;
    if (l <= mid)mmax = query(u << 1, l, r);
    if (r > mid)mmax = max(mmax, query(u << 1 | 1, l, r));
    return mmax;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)scanf("%d", &w[i]);
    build(1, 1, n);
    int l, r;
    while (m--) {
        scanf("%d%d", &l, &r);
        printf("%d\n", query(1, l, r));
    }
    return 0;
}