题意：给一个数列，按如下公式求和。
分析：场上做的时候，傻傻以为是线段树，也没想出题者为啥出log2，就是S(i,j) 的二进制表示的位数。只能说我做题依旧太死板，让求和就按规矩求和，多考虑一下就能发现这个题目应该是另想办法解决的，类似于改代码的题目，直接告诉你C++代码，让你从TLE改成AC，其实真正让你改的是算法，全身都要变。
看了题解，终于明白这道题目的正解算法：
因为S(i,j)的位数在一定范围内是一样的，所以我们可以枚举位数1~35（顶多是2^34），怎么计算（i+j）？继续枚举起点k，然后找满足位数是所枚举的位数的区间（l,r）即(k,l)~(k,r)都是二进制位数为t的，然后统一计算（k,l）~(k.r)的和，其实就是一个l~r的等差序列（r + l）*(r - l + 1) / 2，一个是k的（r-l+1）倍。一直枚举到位数大于数列全部的和。
PS：枚举区间的时候用的是尺取法，很容易懂，就是从起点k开始，直到有不满足的条件，否则l++，然后r直接从l开始，其实计算的时候一般能想得到。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
#define maxn 101010
LL pow2l[],pow2r[],s[maxn];
int main()
{
for(int i=; i<=; i++)
{
pow2l[i]=(1ll<<i);
pow2r[i]=((1ll<<(i+))-);
}
pow2l[]=;
pow2r[]=;
LL ncase,i,j,n,x;
scanf("%I64d",&ncase);
while(ncase--)
{
scanf("%d",&n);
for(i=; i<=n; i++)
{
scanf("%I64d",&x);
s[i]=s[i-]+x;
}
LL ans=;
for(i=; i<=; i++)
{
if(s[n] < pow2l[i-])
break;
LL l=,r=,temp=;
for(j=; j<=n; j++)
{
l = max(l,j);
while(l <= n && s[l] - s[j-] < pow2l[i-])
l++;
r = max(r,l - );
while(r < n && s[r+] - s[j-] >= pow2l[i-] && s[r+]-s[j-] <= pow2r[i-])
r++;
if(r >= l)
temp+=(r-l+)*j+(r+l)*(r-l+)/;
}
ans += temp * i;
}
printf("%I64d\n",ans);
}
return ;
}
AC