B3645 数列前缀和 2

B3645 数列前缀和 2 是指给定一个数列B，求数列B的前缀和从第1项到第2项的和。前缀和是指从数列的第1项开始，逐项相加得到的新数列。根据引用的原则，我们可以通过构建一个数组a，将数列B的差分存储在数组a中，然后求数组a的前缀和得到数列B的前缀和。具体操作如下：
1. 构建一个数组b，使其长度与数列B的长度相同。
2. 将数组b的第1项设为数列B的第1项。
3. 循环遍历数列B的每一项，将数列B的第i项减去数列B的第i-1项，并将结果存储在数组b的第i项。
4. 构建一个数组a，使其长度与数组b的长度相同。
5. 将数组a的第1项设为数组b的第1项。
6. 循环遍历数组b的每一项，将数组b的第i项加上数组b的第i-1项，并将结果存储在数组a的第i项。
7. 数组a即为数列B的前缀和。
8. 求数列B的前缀和从第1项到第2项的和，即为数组a的第2项。

相关问题

B3646 数列前缀和3

### 关于数列前缀和的编程实现

对于数列前缀和问题，在处理涉及频繁查询子数组或子序列和的情况下，使用前缀和是一种高效的方法。通过预先计算并存储从起始位置到当前位置所有元素之和的结果，可以在常量时间内完成任意区间的求和操作。

#### B3646 数列前缀和问题描述
给定一个长度为 n 的整数序列 a_1, a_2, ..., a_n 和 m 次询问，每次询问给出两个正整数 L 和 R (L ≤ R)，要求返回该范围内所有数字的总和 S(L,R)=a_L+a_(L+1)+...+a_R 。为了优化性能，可以构建辅助性的前缀和数组 prefix_sum[] 来加速此类请求的响应速度[^2]。

#include <iostream>
using namespace std;

const int MAXN = 1e5 + 5;
long long nums[MAXN], preSum[MAXN];

int main() {
    int n, q; cin >> n >> q;
    
    // 输入原始数值并初始化前缀和数组
    for(int i=1;i<=n;++i){
        cin>>nums[i];
        preSum[i]=preSum[i-1]+nums[i];  
    }
    
    while(q--){
        int l,r;cin>>l>>r;
        cout<<preSum[r]-preSum[l-1]<<endl;
    }

    return 0;
}

此代码片段展示了如何读取输入数据、建立前缀和表以及快速回答多个区间求和的问题。当面对大量重复性的范围求和需求时，这种方法能显著减少时间复杂度至 O(1)。

哈夫曼树：某文件中有A、B、C、D、E、F和G共7种不同的字符，且每种字符出现的频率如下表所示，函数发f()恰好对应斐波那契数列的第2~8个数值：算法思路、伪代码、以及算法正确性

算法思路：
1. 将每个字符及其频率作为一个节点，构成一个森林。
2. 从森林中选取两个根节点的权值最小的树合并成一棵新树，权值为两个节点权值之和。
3. 将新树重新插入到森林中。
4. 重复步骤2和步骤3，直到森林中只剩下一棵树，即哈夫曼树。
5. 对哈夫曼树进行编码，规定左子树为0，右子树为1，从根节点开始遍历，直到叶子节点，得到每个字符的编码。

伪代码：

哈夫曼树(tree)
    while tree中节点数量 > 1
        选取tree中权值最小的两个节点node1, node2
        将node1和node2合并成一个节点new_node，权值为node1和node2的权值之和
        将new_node插入到tree中
    end while
    return tree

编码(tree, code)
    如果tree为叶子节点
        输出该节点对应的字符和编码code
    否则
        左子树递归调用编码函数，code加上0
        右子树递归调用编码函数，code加上1
    end if

算法正确性：
哈夫曼树是一种最优前缀编码，即每个字符的编码都不是另一个字符编码的前缀。证明如下：
假设存在两个字符x和y，它们的编码分别为a和b，且a是b的前缀，即a=bp（p为一个非空字符串）。
根据哈夫曼树的构造方式，权值较小的节点总是在深度较大的位置，因此x和y在哈夫曼树上的深度一定不同。
不妨设x在y的左侧，即在哈夫曼树上，x的深度小于y的深度。则a的最后一个字符必然是x对应的叶子节点，而b的最后一个字符是y对应的叶子节点。
由于a是b的前缀，故b必然包含a，即a=bp（p为一个非空字符串）。又因为x和y在哈夫曼树上深度不同，故x对应的叶子节点不可能是y对应叶子节点的祖先节点。
因此，a的最后一个字符不可能是y对应的叶子节点，与前面的假设矛盾。
因此，哈夫曼树是一种最优前缀编码。