数据结构¶

树状数组¶

单点更新区间查询

int a[maxn],c[maxn]; //原数组和树状数组

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

void updata(int i,int k) //第 i 个元素加 k
{  
    while(i <= n)
    {
        c[i] += k;
        i += lowbit(i);
    }
}
int getsum(int i) //前i个和
{    
    int res = 0;
    while(i > 0)
    {
        res += c[i];
        i -= lowbit(i);
    }
    return res;
}

区间更新单点查询

//利用原数组的差分数组建树
int a[maxn] = {0},c[maxn]; //原数组和树状数组

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

void updata(int i,int k)  //第 i 个元素加 k
{   
   while(i <= n)
   {

       c[i] += k;
       i += lowbit(i);
   }
}

int getsum(int i) //前i个
{
    int res = 0;
    while(i > 0)
    {
        res += c[i];
        i -= lowbit(i);
    }
    return res;
}

/*
    updata(i,a[i] - a[i-1]);   //差分建树
    //[x,y]区间内加上k
    updata(x,k);         //A[x] - A[x-1]增加k
    updata(y+1,-k);      //A[y+1] - A[y]减少k
    //单点查询 差分建树所以单点查询变成了求和
    int sum = getsum(i);
*/

区间更新区间查询

d 是 a 的差分数组

有 $a_i = \sum_{j=1}^{i}{d_j}$

$\therefore\sum_{i=1}^{r}{a_i} = \sum_{i=1}^{r}{\sum_{j=1}^{i}{d_j}} $

$= \sum_{i=1}^{r}{d_i \times(r-i+1)}$

$ = \sum_{i=1}^{r}{d_i \times(r+1)}-\sum_{i=1}^{r}{d_i \times i}$

所以维护2个树状数组 sum1[i] = d[i]，sum2[i] = d[i]*(i-1)

线段树¶

/*区间和的线段树*/
//建树
void build(ll x, ll l, ll r) {
    if (l == r) {
        scanf("%lld", &sum[x]);
        return;
    }
    ll mid = (l + r) >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
}
//下放懒标记
void pushdown(ll x, ll l, ll r) {
    ll mid = (l + r) / 2;
    lz[x << 1] += lz[x], lz[x << 1 | 1] += lz[x];
    sum[x << 1] += lz[x] * (mid - l + 1), sum[x << 1 | 1] += lz[x] * (r - mid);
    lz[x] = 0;
}
//区间更新
void update(ll x, ll l, ll r, ll gl, ll gr, ll k) {
    if (l >= gl && r <= gr) {
        lz[x] += k;
        sum[x] += (r - l + 1) * k;
        return;
    }
    pushdown(x, l, r);
    ll mid = (l + r) / 2;
    if (gl <= mid) update(x << 1, l, mid, gl, gr, k);
    if (gr > mid) update(x << 1 | 1, mid + 1, r, gl, gr, k);
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
}
//区间和
ll get_sum(ll x, ll l, ll r, ll gl, ll gr) {
    if (l >= gl && r <= gr) return sum[x];
    pushdown(x, l, r);
    ll res = 0;
    ll mid = (l + r) / 2;
    if (gl <= mid) res += get_sum(x << 1, l, mid, gl, gr);
    if (gr > mid) res += get_sum(x << 1 | 1, mid + 1, r, gl, gr);
    return res;
}

并查集¶

int fa[MAXN];
//初始化
void init(int n){
    for(int i = 0; i < n; i++) fa[i] = i;  //父结点是自己
}
//查询并路径压缩
int find(int x){
    if(fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}
//合并
void unite(int x, int y){
    int fx = find(x);
    int fy = find(y);
    fa[fx] = fy; 
}
//查询是否属于同一集合
bool same(int x, int y){
    return find(x) == find(y);
}

带权并查集

int fa[MAXN], value[MAXN]; //父结点  权值
//查询
int find(int x){
    if(x != fa[x]){
        int t = fa[x];
        fa[x] = find(fa[x]);
        value[x] += value[t]; 
        //这时的父亲结点的权值是父结点到根结点的权值
        //所以加上原本自己到父结点的权值就是自己到根结点的权值
    }
    return fa[x];
}
//合并, s是x->y的权值
void unite(int x, int y, int s){
    int px = find(x);
    int py = find(y);
    if(px != py){
        fa[px] = py;
        value[px] = s+value[y]-value[x];
        //x->y->py的权值 = x->px->py的权值，所以得px->py的权值为上式
    }  
}

栈¶

单调栈¶

//求出每个元素左右第一个小于它的元素的下标
for(int i = 1; i <= n; i++)
{
    while(!st.empty() && num[st.top()] > num[i])
    {
        r[st.top()] = i;
        st.pop();
    }
    if(st.empty()) l[i] = -1;
    else if(num[st.top()] == num[i]) l[i] = l[st.top()];
    else l[i] = st.top();
    st.push(i);
}

while(!st.empty())
{
    r[st.top()] = n+1;
    st.pop();
}

可持久化数据结构¶

可持久化线段树(主席树)¶

洛谷 P3834

//一般开32倍空间
const int maxn = 2e5 + 5;
int a[maxn], b[maxn], n, m, tot, q;
int lc[maxn << 5], rc[maxn << 5], sum[maxn << 5], rt[maxn << 5];

void build(int &rt, int l, int r) {
    rt = ++tot, sum[rt] = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(lc[rt], l, mid), build(rc[rt], mid + 1, r);
}

int update(int x, int l, int r, int t) {
    int xx = ++tot;
    lc[xx] = lc[x], rc[xx] = rc[x], sum[xx] = sum[x] + 1;
    if (l == r) return xx;
    int mid = (l + r) >> 1;
    if (t <= mid)
        lc[xx] = update(lc[xx], l, mid, t);
    else
        rc[xx] = update(rc[xx], mid + 1, r, t);
    return xx;
}

int query(int u, int v, int l, int r, int k) {
    int mid = (l + r) >> 1, t = sum[lc[v]] - sum[lc[u]];
    if (l == r) return l;
    if (k <= t) return query(lc[u], lc[v], l, mid, k);
    else return query(rc[u], rc[v], mid + 1, r, k - t);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) scanf("%d", a + i), b[i] = a[i];
    sort(b + 1, b + 1 + n);
    q = unique(b + 1, b + 1 + n) - b - 1;
    build(rt[0], 1, q);
    for (int i = 1; i <= n; i++) {
        int t = lower_bound(b + 1, b + 1 + q, a[i]) - b;
        rt[i] = update(rt[i - 1], 1, q, t);
    }
    int l, r, k;
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", &l, &r, &k);
        printf("%d\n", b[query(rt[l - 1], rt[r], 1, q, k)]);
    }
    return 0;
}

二位前缀和¶

//预处理
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
        dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+matrix[i][j];
//x1, y1, x2, y2 (查询区间)
int res = dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1];