DataStructure-Fenwick-Tree-Sparse-Table

Fenwick Tree (树状数组)

Introduction

树状数组的核心在于高效处理前缀和，并且使用树状结构。

为了方便计算，这里的数组全部使用1-based.

树状数组

如上图所示，$a_i$是原数组的值，而$c_i$是根据$a_i$所生成的树状数组

Template Operations

预处理（区间管辖）

上面的图非常清晰，每一个$c_i$都管辖了对应区间的前缀和，那如何使用代码表示？

给出函数lowbit(x)，返回在二进制下最低位1和后面的0组成的数。

1
2
3
int lowbit(int x) {
  return x & -x;
}

不难发现，$c_i$管辖的区间就是$[x-lowbit(x)+1,x]$.

具体而言，lowbit()函数就是把这个值减去了小于他的最小的二进制组成的幂次。这一个部分在后文详细解释。

区间求和查询

本质上就是二进制的拆解过程。

例如$7=1+2+4$，因此

$$ {\textstyle \sum_{i=1}^{7}a_i}= {\textstyle \sum_{i=1}^{4}a_i} + {\textstyle \sum_{i=5}^{6}a_i} + {\textstyle \sum_{i=7}^{7}a_i}$$

$${\textstyle \sum_{i=1}^{7}a_i} = c_4 + c_6 + c_7$$

一般的，${\textstyle \sum_{i=a}^{b}a_i} = {\textstyle \sum_{i=1}^{b}a_i} - {\textstyle \sum_{i=1}^{a}a_i}$

那如何使用lowbit()实现这个前缀切分的过程？以7为例，考虑下面的程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;

inline long long lowbit(long long x){
    return x & (-x);
}

int main(){
    cout << "Hello world" << endl;
    int x = 7;
    while(x > 0){
        cout << lowbit(x) << endl;
        x -= lowbit(x);
    }
    return 0;
}
1
2
3
4
Hello world
1
2
4

换句话说，$lowbit(7)=1$ ,这个1就代表$a_7$这一个元素，储存在$c_7$中。

接下来更新$x$的值，此时7变成了6，$lowbit(6)=2$，代表$c_6$中储存了2个元素（$a_5,a_6$）。

这样，我们就找到了区间查询的做法：

1
2
3
4
5
6
7
8
9
10
11
12
/*
!区间查询
*/
long long getsum(long long x){
    long long ans = 0;
    while(x > 0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

单点修改

Propositions

（这一段截自OI wiki，讲的太好了）

  • $x \le y$，则$c[x]$和$c[y]$不交或存在包含关系。
  • $c[x]$真包含于$c[x+lowbit(x)]$
  • 对于$x$和$x + lowbit(x)$之间的元素，$c[x]$和$c[y]$严格不交

千言万语不如再看看这张图

  • $height_x=\log_{2}lowbit(x)$
  • $lowbit(x) < lowbit(fa[x])$

基本思路：以$a_i$为起点，沿着树不断往上一直走到头（所有包含这个元素的前缀和都需要修改）

1
2
3
4
5
6
void add(int x, int k) {
  while (x <= n) {  
    c[x] = c[x] + k;
    x = x + lowbit(x);
  }
}

注意，在考虑树状数组的树形态时，我们不考虑树状数组大小的影响，即我们认为这是一棵无限大的树，方便分析。实际实现时，我们只需保证$x \le n$，其中$n$是原数组长度。

因此，我们给出完整的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct fenwick_1
//
{
    int N;
    long long C[MAXN];

    void init(int n){
        N = n;
        memset(C, 0, sizeof(C));
    }

    void addSingle(int pos, long long val) {
        for(int i = pos; i <= N; i += lowbit(i)){
            C[i] += val;
        }
    }

    long long rangeAsk(int pos) {
        long long ans = 0;
        for(int i = pos; i > 0; i -= lowbit(i)){
            ans += C[i];
        }
        return ans;
    }

    long long rangeAsk2(int l, int r) {
        return rangeAsk(r) - rangeAsk(l - 1);
    }
};

建树

在建树操作中，可以首先全部初始化为0，然后单点插入$n$个元素，时间复杂度$O(n\log n)$。

对于上述两种基本操作，均可以达到$O(\log n)$的时间复杂度。

区间修改和单点查询

以下内容节选自OI Wiki

考虑序列 $a$ 的差分数组 $d$，其中 $d[i] = a[i] - a[i-1]$。由于差分数组的前缀和就是原数组，所以

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

一样地，我们考虑将查询区间和通过差分转化为查询前缀和。那么考虑查询 $a[1 \dots r]$ 的和，即 $\sum_{i=1}^{r} a_i$，进行推导：

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

观察这个式子，不难发现每个 $d_j$ 总共被加了 $r-j+1$ 次。接着推导：

$$
\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
$$

$\sum_{i=1}^{r} d_i$ 并不能推出 $\sum_{i=1}^{r} d_i \times i$ 的值，所以要用两个树状数组分别维护 $d_i$ 和 $d_i \times i$ 的和信息。

使用差分数组的优势在于对于区间内部的点，同增不会改变差分的值，因此，区间修改可以转化为对差分数组的单点修改，之后使用模版即可。

因此，我们在额外维护两个数组的情况下，可以实现如下操作：

已知模版操作：区间求和查询 & 单点修改

  • 区间修改：对差分数组的单点修改
  • 区间求和：对两个差分数组（$d_i * i$）的单点查询
  • 单点操作就是区间操作的退化情况

截至，我们就可以完成四种一维数组的基本操作了！值得一题的是，在这里我们并不需要维护对原数组的树状数组，我们应该维护两个差分数组的树状数组，并转化为相对应的模版操作。

给出代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
struct fenwick_2
{
    int N;
    long long C1[MAXN];
    long long C2[MAXN];

    void init(int n){
        N = n;
        memset(C1, 0, sizeof(C1));
        memset(C2, 0, sizeof(C2));
    }

    void addRange1(int pos, long long val){
        //对于差分数组的单点修改操作
        for(int i = pos; i <= N; i += lowbit(i)){
            C1[i] += val;
            C2[i] += val * pos;
        }
    }

    void addRange2(int posl, int posr, long long val){
        //对差分数组使用两次单点修改操作，就可以得到区间修改
        addRange1(posl, val);
        addRange1(posr + 1, -val);
    }

    long long askRange1(int pos){
        //从1到pos的区间求和
        long long ans = 0;
        for(int i = pos; i > 0; i -= lowbit(i)) {
            ans += (pos + 1)*C1[i] - C2[i];
        }
        return ans;
    }

    long long askRange2(int l, int r){
        return askRange1(r) - askRange1(l - 1);
    }

    //退化为单点的修改和查询
    void Addsingle(int pos, long long val){
        addRange2(pos, pos, val);
    }

    long long Asksingle(int pos){
        return askRange2(pos, pos);
    }

};

二维树状数组

问题重述

给定一个二维数组$A_{m \times n}$，要求实现如下操作：

  • 单点修改$A[x][y]$
  • 单点查询$A[x][y]$
  • 区间和查询，查询左上角为$(x_1,y_1)$右下角为$(x_2,y_2)$的矩阵和
  • 区间修改，左上角为$(x_1,y_1)$右下角为$(x_2,y_2)$的矩阵统一加上$x$

建立新的树状数组

在一维树状数组中，数组$C[x]$记录了的是右端点为$x$、长度为$lowbit(x)$的区间的区间和。

那么我们也可以类似地定义$C[x][y]$记录的是右下角为$(x,y)$，高为 $lowbit(x)$，宽为 $lowbit(y)$ 的区间的区间和。

这样的过渡非常自然，我们因此也可以类似完成上面的4个基本操作。

单点修改 & 区间查询（模版操作）

单点修改的基本思路保持不变：沿着最开始的叶节点不断向上修改祖先节点的值，最终到达最大值。

在二维数组中，修改一个单点，那么对于横轴和纵轴，相当于套两层循环，并且不断的迭代，代码同理：

1
2
3
4
5
6
7
void add(int x, int y, int v) {
  for (int i = x; i <= n; i += lowbit(i)) {
    for (int j = y; j <= m; j += lowbit(j)) {
      c[i][j] += v;
    }
  }
}

对于子矩阵的查询，先给出查询左上角起点为$(1,1)$的矩阵的和的公式：

1
2
3
4
5
6
7
8
9
10
11
//ask for the submatrix (1,1) -> (x,y)
    long long ask(int x, int y){
        long long ans = 0;
        for(int i = x; i > 0; i -= lowbit(i)){
            for(int j = y; j > 0; j -= lowbit(j)){
                ans += C[i][j];
            }
        }

        return ans;
    }

在二维数组中，${\textstyle \sum_{i=a}^{b}a_i} = {\textstyle \sum_{i=1}^{b}a_i} - {\textstyle \sum_{i=1}^{a}a_i}$ 需要被推广，也就是

Sum

这样，最基本的模版操作就可以推广了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstring>

const int MAXM = 100000;
const int MAXN = 100000;

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

/**
 * @brief only for two operations: modify a single point and sum a submatrix
 * 
 */
struct fenwick_2d_1{
    int m,n;//size
    long long C[MAXM][MAXN];//fenwick tree

    fenwick_2d_1(int m_, int n_){
        m = m_;
        n = n_;
        memset(C, 0, sizeof(C));
    }
    
    /**
     * @brief Modify a single element
     * 
     * @param x x-index (1-based)
     * @param y y-index (1-based)
     * @param val plus val
     */
    void add(int x, int y, long long val){
        for(int i = x; i <= m; i += lowbit(i)){
            for(int j = y; j < n; j += lowbit(j)){
                C[i][j] += val;
            }
        }
    }

    //ask for the submatrix (1,1) -> (x,y)
    long long ask(int x, int y){
        long long ans = 0;
        for(int i = x; i > 0; i -= lowbit(i)){
            for(int j = y; j > 0; j -= lowbit(j)){
                ans += C[i][j];
            }
        }

        return ans;
    }

    //(p,q) -> (x,y)
    long long ask_sub(int p, int q, int x, int y){
        return ask(x, y)-ask(p - 1, y)-ask(q - 1, y)+ask(p, q);
    }
};

使用差分数组完成四个基本操作

本质上还是一维变二维的过程。

首先给出二维条件下差分数组的定义：

$$d[i][j]=a[i][j]−a[i−1][j]-a[i][j−1]+a[i−1][j−1]$$

此处需要保证前缀和和差分是一对逆运算。

区间修改和单点查询

对于区间修改，同理，对于差分数组来说只有四个顶角的点会发生变动（），证明略。

对于单点查询，可以转化为对差分数组的区间查询。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
struct fenwick_2d_2
{
    int m, n;
    long long C[MAXM][MAXN];//此处维护差分数组
    void init(int m_, int n_){
        m = m_;
        n = n_;
        memset(C, 0, sizeof(C));
    }

    /**
     * @brief submatrix(1,1) -> (x,y) all add val
     * 
     * @param x 
     * @param y 
     * @param val 
     * 这里的代码和上一个代码的add完全相同，但是意义不一样，因为这里的C维护的是差分数组
     */
    void add(int x, int y, long long val){
        for(int i = x; i <= m; i += lowbit(i)){
            for(int j = y; j <= n; j += lowbit(y)){
                C[i][j] += val;
            }
        }
    }

    /**
     * @brief submatrix(x1, y1) -> (x2, y2) all adds x
     * 
     * @param x1 
     * @param y1 
     * @param x2 
     * @param y2 
     * @param x 
     */
    void range_add(int x1,int y1,int x2,int y2,long long x) {
        add(x1,y1,x);
        add(x1,y2+1,-x);
        add(x2+1,y1,-x);
        add(x2+1,y2+1,x);
    }

    /**
     * @brief return the value of index (x,y)
     * 
     * @param x 
     * @param y 
     * @return long long 
     */
    long long ask(int x,int y)
    {
        long long ret=0;
        for(int i = x; i > 0; i -= lowbit(i)){
            for(int j = y;j > 0;j -= lowbit(j)){
                ret += C[i][j];
            }
        }
            
        return ret;
    }
};

更加复杂的一般化？

如果我需要同时支持四种操作？此时会更加复杂，贴上来自OI wiki的补充证明：

对于点 $(x, y)$，它的二维前缀和可以表示为：

$$
\sum_{i=1}^{x} \sum_{j=1}^{y} \sum_{h=1}^{i} \sum_{k=1}^{j} d(h, k)
$$

原因就是差分的前缀和的前缀和就是原本的前缀和。

和一维树状数组的「区间加区间和」问题类似，统计 $d(h, k)$ 的出现次数，为 $(x - h + 1) \times (y - k + 1)$。

然后接着推导：

$$
\sum_{i=1}^{x} \sum_{j=1}^{y} \sum_{h=1}^{i} \sum_{k=1}^{j} d(h, k) = \sum_{i=1}^{x} \sum_{j=1}^{y} d(i, j) \times (x - i + 1) \times (y - j + 1)
$$
$$= \sum_{i=1}^{x} \sum_{j=1}^{y} d(i, j) \times (xy + x + y + 1) - d(i, j) \times i \times (y + 1) - d(i, j) \times j \times (x + 1) + d(i, j) \times i \times j$$

因此，在二维数组中，需要额外维护4个差分数组！

  • 区间修改：对差分数组做操作
  • 区间查询：对差分数组做操作
  • 单点查询：退化，可以转化为对一个1*1的子矩阵进行查询
  • 单点修改：退化，可以转化为对一个1*1的子矩阵进行修改
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
struct fenwick_2d_3
{
    int m, n;
    long long C1[MAXM][MAXN];
    long long C2[MAXM][MAXN];
    long long C3[MAXM][MAXN];
    long long C4[MAXM][MAXN];

    void init(int m,int n)
    {
        this->n = n;
        this->m = m;
        memset(C1,0,sizeof(C1));
        memset(C2,0,sizeof(C2));
        memset(C3,0,sizeof(C3));
        memset(C4,0,sizeof(C4));
    }

    //区间修改
    /**
     * @brief Add val for single element (x,y)
     * 
     * @param x 
     * @param y 
     * @param val 
     */
    void add(int x, int y, long long val) {
        for(int i = x;i <= m;i += lowbit(i))
        {
            for(int j = y;j <= n;j += lowbit(j))
            {
                C1[i][j] += val;
                C2[i][j] += val * x;
                C3[i][j] += val * y;
                C4[i][j] += val * x * y;
            }
        }
    }

    /**
     * @brief Add val for all elements in the submatrix 
     * 
     * @param x 
     * @param y 
     * @param val 
     */
    void add_submatrix(int x1, int y1, int x2, int y2, long long val) {
        add(x1,y1,val);
        add(x1,y2+1,-val);
        add(x2+1,y1,-val);
        add(x2+1,y2+1,val);
    }

    //区间查询
    /**
     * @brief the sum of the submatrix (1,1) -> (x,y)
     * 
     * @param x 
     * @param y 
     * @return long long 
     */
    long long rangeAsk1(int x, int y){
        long long ans = 0;
        for(int i = x; i > 0; i -= lowbit(i)){
            for(int j = 0; j > 0; j -= lowbit(j)){
                ans += (x + 1)*(y + 1)*C1[i][j];
                ans -= (y + 1)*C2[i][j] + (x + 1)*C3[i][j];
                ans += C4[i][j];
            }
        }
        return ans;
    }

    long long rangeAsk2(int x1, int y1, int x2, int y2){
        return rangeAsk1(x2,y2) - rangeAsk1(x1-1,y2) - rangeAsk1(x2,y1-1) + rangeAsk1(x1-1,y1-1);
    }

    //单点查询
    long long ask(int x,int y)
    {
        return rangeAsk2(x, y, x, y);
    }

    //单点修改的退化情况
    void modifySingle(int x, int y, long long val){
        add_submatrix(x, y, x, y, val);
    }
};


至此，我们已经实现了四种最基本的模版操作！

权值树状数组

TBD

一个序列$a[x]$的权值数组$b[x]$，满足$b[x]$的值为$x$在$a[\ ]$中的出现次数。在权值数组中，值与值之间的相对关系比值的绝对大小要更加重要。因此，如果对于值域过大的情况，可以先使用离散化操作后再建立等效的权值数组。另外，权值数组是原数组无序性的一种表示：它重点描述数组的元素内容，忽略了数组的顺序，若两数组只是顺序不同，所含内容一致，则它们的权值数组相同。

由于权值数组考虑值与值之间的大小关系，因此将重点放在查询排名而并非区间和上面。

Question1

给定一个数组，包含两种操作：

  • 单点修改
  • 查询全局第k小的元素

Sparse Table (ST)

倍增

倍增法，顾名思义就是「成倍增长」。我们在进行递推时，如果状态空间很大，通常的线性递推无法满足时间与空间复杂度的要求，那么我们可以通过成倍增长的方式，只递推状态空间中在 k 的整数次幂位置上的值作为代表。当需要其他位置上的值时，我们通过「任意整数可以表示成若干个$k$的次幂项的和」这一性质，使用之前求出的代表值拼成所需的值。所以使用倍增算法也要求我们递推的问题的状态空间关于$k$的次幂具有可划分性。通常情况下$k$取$2$。

倍增思想可以解决RMQ问题。

倍增例题

倍增

在m很大时，我们可以对$m$进行二进制分解，而预处理的数组就是对于$2^j$次跳跃的处理！

倍增的关键就是在于将一个很长的模拟过程分割成已经预处理好的小段。

预处理

ST表的核心是一个二维数组 st[i][j]，表示从数组的第$i$个位置开始，长度为 $2^j$的区间内的最值（最小值或最大值）。

假设输入数组为 arr，其长度为$n$。则 st[i][j] 的含义如下：

$$st[i][j]=\min /\max(arr[i],arr[i+1],…,arr[i+2^j−1])$$

我们需要根据输入数组 arr 构建这个二维数组。

至于预处理的核心过程，我们可以采用动态规划的思想，j从小到大，因为保证是2的整数幂次，所以能够实现快速的预处理填充过程。

RMQ Problem

给出模版题：求区间中的最大值

如果使用传统的二进制倍增算法，在做完预处理之后对于区间进行二进制切分再统计对应的分块即可。这样对于多次问询的情况可以极大提升时间复杂度。

但是这样仍然不太好，因为二进制的严格切分其实会变得非常松散（最坏的情况就是$O(\log n)$），如果我们只是希望求区间的最值（可重复贡献问题），我们可以进行稀疏的切分，哪怕两份切分之间存在重叠部分也没有关系，因为我们已经预处理好了，最后只是一个查表的事情。

这样，倍增切分的时间复杂度就保持在常数级别。

注意，只有可重复贡献问题才可以重叠区间！如果是对于求区间和，就必须严格进行二进制的切分之后再运算。

代码实现

注意这里是 0-based

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
 * @Author: Xiyuan Yang   xiyuan_yang@outlook.com
 * @Date: 2025-04-01 21:20:31
 * @LastEditors: Xiyuan Yang   xiyuan_yang@outlook.com
 * @LastEditTime: 2025-04-01 21:20:47
 * @FilePath: /20250331_fenwick/template/ST_RMQ.cpp
 * @Description: 
 * Do you code and make progress today?
 * Copyright (c) 2025 by Xiyuan Yang, All Rights Reserved. 
 */
#include <iostream>
#include <cmath>
using namespace std;

const int MAXN = 1e6 + 5; // 输入数组的最大长度
const int LOG = 20;       // log2(MAXN) 的上界

int st[MAXN][LOG]; // ST表，st[i][j]表示从i开始长度为2^j的区间的最小值
int arr[MAXN];     // 输入数组
int n;             // 数组长度

// 预处理函数
void preprocess() {
    // 初始化长度为 2^0 的区间
    for (int i = 0; i < n; ++i) {
        st[i][0] = arr[i];
    }

    // 动态规划填充表格
    for (int j = 1; j < LOG; ++j) { // 区间长度从 2^1 到 2^(LOG-1)
        for (int i = 0; i + (1 << j) <= n; ++i) { // 确保区间不越界
            st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

// 查询 [L, R] 区间的最小值
int query(int L, int R) {
    int len = R - L + 1; // 查询区间的长度
    int k = log2(len);   // 找到最大的 k 满足 2^k <= len
    return min(st[L][k], st[R - (1 << k) + 1][k]);
}

int main() {
    // 输入数组长度和元素
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    // 预处理 ST 表
    preprocess();

    // 查询操作
    int q; // 查询次数
    cin >> q;
    while (q--) {
        int L, R;
        cin >> L >> R; // 查询区间 [L, R]
        cout << query(L, R) << endl; // 输出区间最小值
    }

    return 0;
}

ST表例题

A 是某公司的 CEO，每个月都会有员工把公司的盈利数据送给 A，A 是个与众不同的怪人，A 不注重盈利还是亏本，而是喜欢研究「完美序列」：一段连续的序列满足序列中的数互不相同。

A 想知道区间 [L,R] 之间最长的完美序列长度。

第一行两个整数 N,M，N 表示连续 N 个月，编号为 0 到 N-1，M 表示询问的次数；

第二行 N 个整数，第 i 个数表示该公司第 i 个月的盈利值 $a_i$；

接下来 M 行每行两个整数 L,R，表示 A 询问的区间。

思路

记 $f(i)$ 表示以第 $i$ 个位置为结尾的最长完美序列的左端点位置。容易发现$ f(i)$ 是不降的。对于一个$ [l,r]$ 的询问，将区间中的点分成左右两部分：左边的点满足 $f(i)<L$ ，右边的点满足$ f(i)≥L$ 。对于左边的点可以直接算出答案，对于右边的点可以用 ST 表区间询问求得答案。

此处ST表储存的是对应区间每一个i在无限延伸的情况下满足i为右端点可以达到的最长长度。对于这个左端点，其满足可重复贡献问题，因此可以使用ST表解决。如果并非无限延伸而是限制了区间，那么无法使用动态规划的思路构建ST表，因为很明显其并不满足结合律，无法将小问题简单合并成大问题，无法使用ST表

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

const int MAXN = 2e5 + 5; // 数组最大长度
const int LOG = 20;       // log2(MAXN) 的上界

int f[MAXN];              // f[i] 表示以第 i 个位置为结尾的最长完美序列的左端点位置
int st[MAXN][LOG];        // ST表，st[i][j]表示从i开始长度为2^j的区间内的最小值
int last[2][1000005];         // last[x]表示数字x最后一次出现的位置
int arr[MAXN];            // 输入数组
int n;                    // 数组长度

inline int getpos(int x){
    if(x >= 0) return 0;
    else return 1;
}
// 预处理函数：计算 f[i]
void preprocess_f() {
    memset(last, -1, sizeof(last)); // 初始化 last 数组
    for (int i = 0; i < n; ++i) {
        if (i > 0 && last[getpos(arr[i])][abs(arr[i])] >= f[i - 1]) {
            f[i] = last[getpos(arr[i])][abs(arr[i])] + 1;
        } else {
            // 如果 arr[i] 是第一次出现，f[i] = f[i-1]
            f[i] = (i > 0 ? f[i - 1] : 0);
        }
        last[getpos(arr[i])][abs(arr[i])] = i; // 更新 arr[i] 的最后一次出现位置
    }
}

// 预处理 ST 表
void preprocess_st() {
    for (int i = 0; i < n; ++i) {
        st[i][0] = i - f[i] + 1;
        //cout << st[i][0] << " ";
    }
    //cout << endl;

    for (int j = 1; j < LOG; ++j) { 
        for (int i = 0; i + (1 << j) - 1 < n; ++i) { 
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            //cout << st[i][j] << " ";
        }
        //cout << endl;
    }
}

//no restriction here
int query_max(int L, int R) {
    int len = R - L + 1; 
    int k = log2(len);
    //cout << "k" << k << endl;
    return max(st[L][k], st[R - (1 << k) + 1][k]);
}

//Binary search
int binary_search(int L, int R, int target) {
    int low = L, high = R;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (f[mid] >= target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

int main() {
    cin >> n;
    int m;
    cin >> m; 

    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    preprocess_f();
    preprocess_st();

    

    
    while (m--) {
        int L, R;
        cin >> L >> R; 
        int p = binary_search(L, R, L);
        //cout << "p" << p << endl;

        int left_len = (p > L) ? (p - L) : 0;

        int right_len = 0;
        if (p <= R) {
            right_len = query_max(p, R);
            //cout << "rightlen" << right_len << endl;
        }

        cout << max(left_len, right_len) << '\n';
    }

    return 0;
}
Algorithm
#tutorial #C/C++ #Data Structure #Tree #Fenwick Tree #Sparse Table
DataStructure-Fenwick-Tree-Sparse-Table
https://xiyuanyang-code.github.io/posts/DataStructure-Fenwick-Tree-Sparse-Table/
Author
Xiyuan Yang
Posted on
March 30, 2025
Updated on
April 1, 2025
Licensed under