关于树状数组做线段树的问题
查看原帖
关于树状数组做线段树的问题
372299
超级玛丽王子楼主2020/9/7 21:22

以前打树状数组都能过的啊 为什么这样突然过不了了

#include <bits/stdc++.h>
#define int long long
#define MAXN 100000
using namespace std;
int n,m,tree1[MAXN+5],tree2[MAXN+5],now,last,opt,x,y,k;
inline unsigned int read(){
    char ch=getchar();
    long long x=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return x*f;
}
inline int lowbit(int x) {
    return x & (-x);
}
inline void add(int x, int d) {
	int i=x;
    while(x<=n) {
        tree1[x] += d;
        tree2[x] += d * (i - 1);
        x += lowbit(x);
    }
}
inline int Sum(int i) {
    int sum=0,x=i;
    while(i>0) {
        sum += x * tree1[i] - tree2[i];
        i -= lowbit(i);
    }
    return sum;
}
signed main(void) {
	n=read(),m=read();
	for(int i=1;i<=n;i++) {
		now=read();
		add(i,now-last);
		last=now;
	}
	for(int i=0;i<m;i++) {
		opt=read(),x=read(),y=read(),k;
		if(opt&1) k=read(),add(x,k),add(y+1,-k);
		else printf("%d\n",Sum(y)-Sum(x-1));
	}
}
2020/9/7 21:22
加载中...