2026年8月29日（前缀和，差分）
2026-08-29 10:11:17
发布于：广东
7阅读
0回复
0点赞
//前缀和 前缀的和
//pre[N]//pre[i]表示前i个元素的和//前缀最大值，后缀最大值，前缀异或和
1 4 7 10 13 16 19 22 25 28 31 34 37 a[N]
pre[N]:前缀和数组
pre[1]=1 //前1个元素的和
pre[2]=1+4 //前2个元素的和
pre[3]=12
pre[4]=22
pre[5]=1+4+7+20+13=35
pre[6]=pre[5]+16=51
pre[7]=pre[6]+19=70;
pre[i]=pre[i-1]+a[i]
//动态规划 DP
//1.记忆化 //用一个数组存储一个指定的答案//pre[i]表示前i个元素的和
//2.状态转移方程 //利用已知去推导未知pre[i]=pre[i-1]+a[i]
求区间[l,r]的和
[1,r]-[1,l-1] -->pre[r]-pre[l-1]
//前缀和
for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
//前缀最大值;
pre_mx[N];pre_mx[i]前i个元素的最大值
for(int i=1;i<=n;i++)pre_mx[i]=max(pre_mx[i-1],a[i]);
//后缀最大值
suf_mx[N];suf_mx[i]后i个元素的最大值
for(int i=n;i>=1;i--)suf_mx[i]=max(suf_mx[i+1],a[i]);
//前缀异或和 | & ^
前i个元素^起来的值,异或本身就具有前缀性
pre_xor[N] pre_xor[i]=前i个元素的异或和
for(int i=1;i<=n;i++)pre_xor[i]=pre_xor[i-1]^a[i];
xor([l,r])
pre_xor[r]^pre_xor[l-1]
100110011
111000111 ^
011110100 //同为0，异为1/不进位的加法
这里空空如也
有帮助，赞一个