RT.为甚么这题我树状数组A了，线段树TLE了？？？
AC code:

#include <bits/stdc++.h>
#define int long long
#define lowbit(x) (x &(- x))
using namespace std;
const int N = 1e6 + 1;
int a[N], b[N], p[1000], n, m, W;
int read () {
	int num = 0, fs = 1;
	char ch = getchar ();
	while ( ( ch < '0' || ch > '9' ) && ch != '-' )	ch = getchar ();
	if ( ch == '-' )	fs = - 1, ch = getchar ();
	while ( ch >= '0' && ch <= '9' ) num = num * 10 + ch - '0', ch = getchar();
	return num * fs;
}
void write(int x) {
	if(x < 0) {
		putchar('-');
		x = - x;
	}
	if(x < 10) {
		putchar(x + '0');
		return ;
	}
	write(x / 10);
	putchar(x % 10 + '0');
}
int check(int &x, int y) {
	int ans = 0;
	while(x > y) {
		x = x - y;
		y = y * 2;
		ans ++;
	}
	return ans;
}
void Up1 (int x, int y) {
	if(x > n) return ;
	a[x] += y;
	Up1 (x + lowbit(x), y);
}
void Up2 (int x, int y) {
	if(x > n) return ;
	b[x] += y;
	Up2 (x + lowbit(x), y);
}
int Down1 (int x) {
	if(x == 0)	return 0;
	return a[x] + Down1(x - lowbit(x));
}
int Down2 (int x) {
	if(x == 0)	return 0;
	return b[x] + Down2(x - lowbit(x));
}
signed main () {
	n = read(), m = read(), W = read();
	p[0] = 1;
	for(int i = 1; i <= 63; i ++)	p[i] = p[i - 1] << 1;
	int pro = 0, ans = 0;
	for(int i = 1; i <= n; i ++) {
		int x = read();
		Up1(i, x - pro);
		Up2(i, (x - pro) * (i - 1));
		pro = x; ans += x;
	}
	while(m --) {
		int L = read(), R = read(), d = read();
		Up1(L, d), Up1(R + 1, - d);
		Up2(L, (L - 1) * d), Up2(R + 1, R * - d);
		ans += (R - L + 1) * d;
		int w = W, l = 1, r = n;
		int tmp = check(w, ans), cnt = 0;
		while(l <= r) {
			int mid = (l + r) >> 1;
			if((Down1(mid) * mid - Down2(mid)) * p[tmp] < w)	cnt = mid, l = mid + 1;
			else	r = mid - 1;
		}
		write(tmp * n + cnt);
		putchar(10);
	}
	return 0;
}

TLE code:

#include <bits/stdc++.h>
#define int long long
#define lowbit(x) (x & (- x))
using namespace std;
const int N = 1e6 + 1;
int n, q, W, p[10010], sum[N], add[N], a[N];
int read () {
	int num = 0, fs = 1;
	char ch = getchar ();
	while ( ( ch < '0' || ch > '9' ) && ch != '-' )	ch = getchar ();
	if ( ch == '-' )	fs = - 1, ch = getchar ();
	while ( ch >= '0' && ch <= '9' ) num = num * 10 + ch - '0', ch = getchar();
	return num * fs;
}
int write(int x) {
	if(x < 0) {
		putchar('-');
		x = - x;
	}
	if(x < 10) {
		putchar(x + '0');
		return 0;
	}
	write(x / 10);
	putchar(x % 10 + '0');
}
int check(int &x, int y) {
	int ans = 0;
	while(x > y) {
		x = x - y;
		y = y * 2;
		ans ++;
	}
	return ans;
}
void Build(int l,int r,int rt){
	if(l==r){
		sum[rt]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	Build(l,mid,rt*2);
	Build(mid+1,r,rt*2+1);
	sum[rt]=sum[rt*2]+sum[rt*2+1];
	return ;
}
void PushDown(int rt,int ls,int rs){
	if(add[rt]){
		add[rt*2]+=add[rt];
		add[rt*2+1]+=add[rt];
		sum[rt*2]+=add[rt]*ls;
		sum[rt*2+1]+=add[rt]*rs;
		add[rt]=0;		
	}
	return ;
}
int Query(int l,int r,int L,int R,int rt){
	if(l<=L&&R<=r)	return sum[rt];
	int mid=(L+R)>>1;
	PushDown(rt,mid-L+1,R-mid);
	if(r<=mid)	return Query(l,r,L,mid,rt*2);
	else if(l>=mid+1)	return Query(l,r,mid+1,R,rt*2+1);
	else	return Query(l,mid,L,mid,rt*2)+Query(mid+1,r,mid+1,R,rt*2+1);
}
void Update(int l,int r,int s,int L,int R,int rt){
	if(l<=L&&R<=r){
		sum[rt]+=(r-l+1)*s;
		add[rt]+=s;
		return ;
	}
	int mid=(L+R)>>1;
	PushDown(rt,mid-L+1,R-mid);
	if(r<=mid)	Update(l,r,s,L,mid,rt*2);
	else if(l>mid)	Update(l,r,s,mid+1,R,rt*2+1);
	else Update(l,mid,s,L,mid,rt*2),Update(mid+1,r,s,mid+1,R,rt*2+1);
	sum[rt]=sum[rt*2]+sum[rt*2+1];
	return ;
}
signed main () {
	n = read(), q = read(), W = read();
	int ans = 0;
	p[0] = 1;
	for(int i = 1; i <= 63; i ++)	p[i] = p[i - 1] << 1;
	for(int i = 1; i <= n; i ++)	a[i] = read(), ans += a[i];
	Build(1, n, 1);
	while (q --) {
		int L = read(), R = read(), d = read();
		Update (L, R, d, 1, n, 1); ans += d * (R - L + 1);
		int w = W;
		int tmp = check(w, ans);
		int l = 1, r = n, cnt = 0;
		while(l <= r) {
			int mid = (l + r) >> 1;
			if(w > Query(1, mid, 1, n, 1) * p[tmp])	cnt = mid, l = mid + 1;
			else	r = mid - 1;
		}
		write(tmp * n + cnt);
		putchar(10);
	}
	return 0;
}