前缀和

前缀和：对于一个长度为n的列表a，前缀和为：

sum[i]=a[0]+a[1]+...+a[i] 

前缀和的性质： 

第一条性质用于处理出前缀和：

  Sum[i]=Sum[i-1]+a[i]

第二条性质可以在O(l)的时间内求出区间和：

  a[l]+....+a[r] =Sum[r]-Sum[l-1]

前缀和模板标准写法

def get_persum(a): #下标从0开始n=len(a)sum=[0]*nsum[0]=a[0]for i in range(1,n):sum[i]=sum[i-1]+a[i]#快速求区间之和
def get_sum(sum,l,r):if l==0:return sum[r]else:return sum[r]-sum[l-1]a=[1,2,3,4,5]
print("a=",a)
print("sum=",sum)

例题1： 异或和—位运算

题目描述

给定一个数组 Ai，分别求其每个子段的异或和，并求出它们的和。或者说，对于每组满足 1≤L≤R≤n的 L, R，求出数组中第 L 至第 R 个元素的异或和。然后输出每组 L, R 得到的结果加起来的值。

输入格式

输入的第一行包含一个整数 nn。

第二行包含 n 个整数 Ai，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例输入

5
1 2 3 4 5

样例输出

39

代码实现：

        这个用前缀和写的代码可以通过90%，简单好理解并且拿到的分比较高

n=int(input())
a=list(map(int,input().split()))
ans=0for L in range(n):sum1=0for R in range(L,n):sum1^=a[R]ans+=sum1print(ans)

 这个是100%通过的代码

n = int(input())
a = [int(x) for x in input().split()]
ans = 0
for k in range(21):            # 所有a不超过20位zero, one = 1, 0           # 统计第k位的0和1的数量cnt, sum = 0, 0            #cnt用于统计第k位有多少对si⊕sj =1for i in range(n):v = (a[i] >> k) & 1    # 取a[i]的第k位sum ^= v               # 对所有a[i]的第k位做异或得到sum，sum等于0或者1if sum == 0:           # 前缀和为0zero += 1          # 0的数量加1cnt += one         # 这次sum=0，这个sum跟前面等于1的sum异或得1else:                  # 前缀异或为1one += 1           # 1的数量加1cnt += zero        # 这次sum=1，这个sum跟前面等于0的sum异或得1ans += cnt * (1 << k)      # 第k位的异或和相加
print(ans)

例题 2：求和

 代码

        利用前缀和思想求后缀和，计算后缀和数组C，C1为a2到an的和,C2为 a3到an的和

n=int(input())
a=list(map(int,input().split()))
ans=0c=[0]*n
c[0]=sum(a)-a[0]for i in range(1,n):c[i]=c[i-1]-a[i]for i in range(n):ans+=a[i]*c[i]print(ans)