template<class T>
struct rsq_add_segt {
	explicit rsq_add_segt(size_t sz = 0, const T &val = 0) {
		for(d=1; d<sz; d<<=1);
		t.assign(d*2, {val, {}});
	}
	
	rsq_add_segt(const vector<auto> &vals): rsq_add_segt(size(vals)) {
		for(size_t i=0; i<size(vals); ++i) t[i+d].first = vals[i];
		for(size_t i=d; i-->1; ) t[i].first = t[i*2].first + t[i*2+1].first;
	}
	
	void add(size_t l, size_t r, const T &val) {
		if(l>=r) return ;
		_add(l, r, val, 0, d, 1);
	}
	
	T operator()(size_t l, size_t r) const {
		if(l>=r) return {};
		return _calc(l, r, 0, d, 1);
	}
	
	private:
	size_t d;
	//t[i] = pair of #(sum on range of node) and #(total additions on range of node)
	vector<pair<T,T>> t;
	
	void _add(size_t i, size_t j, const T &val, size_t l, size_t r, size_t v) {
		//adding to whole range
		if(i==l && j==r){
			//sum increases by value * length_of_range
			t[v].first+=val*T(r-l);
			//total addition increases by value
			t[v].second+=val;
			return ;
		}
		size_t m = (l+r)>>1;
		if(i<m) _add(i,min(j,m),val,l,m,v*2);
		if(m<j) _add(max(i,m),j,val,m,r,v*2+1);
		//update current node: sum on range is sum of children + own addition
		t[v].first = t[v*2].first + t[v*2+1].first + t[v].second * T(r-l);
	}
	
	T _calc(size_t i, size_t j, size_t l, size_t r, size_t v) const {
		//sum of whole range already known
		if(i==l && j==r) return t[v].first;
		size_t m = (l+r)>>1;
		return 
		//query splited to children
		(j<=m ? _calc(i,j,l,m,v*2) : i>=m ? _calc(i,j,m,r,v*2+1)
		 : _calc(i,m,l,m,v*2) + _calc(m,j,m,r,v*2+1))
		//and adding own addition
		  + t[v].second * T(j-i);
	}
};

Two ways for each. Sum on range $$$[L, R)$$$ is equals to

• (sum on prefix R-1) — (sum on prefix L-1)

• (sum on suffix L) — (sum on suffix R)

Similar, add $$$x$$$ on range $$$[L, R)$$$ is

• add $$$x$$$ to prefix R-1 and subtract $$$x$$$ from prefix L-1

• add $$$x$$$ to suffix L and subtract $$$x$$$ from suffix R

template<class T>
struct rsq_add {
	explicit rsq_add(size_t sz = 0): f(sz) {}
	
	rsq_add(const vector<auto> &vals): f(size(vals)) {
		for(size_t i=0; i<size(vals); ++i) {
			T x = vals[i]; if(i) x-=T(vals[i-1]);
			f[i].first+=x;
			f[i].second+=x*T(i);
			if(size_t j = i|(i+1); j<size(f)) {
				f[j].first+=f[i].first;
				f[j].second+=f[i].second;
			}
		}
	}
	
	void add(size_t l, size_t r, const T &val) {
		if(l>=r) return ;
		add_suf(l, val);
		add_suf(r, -val);
	}
	
	T operator()(size_t l, size_t r) const {
		if(l>=r) return T();
		return sum_until(r) - sum_until(l);
	}
	
	inline T operator[](size_t i) const { return sum_until(i+1) - sum_until(i); }
	
	private:
	vector<pair<T,T>> f;
	
	void add_suf(size_t pos, const T &val) {
		T m = val * T(pos);
		for(size_t i=pos; i<size(f); i|=i+1) 
			f[i].first+=val, f[i].second+=m;
	}
	
	T sum_until(size_t pos) const {
		T a{}, b{};
		for(size_t i=pos; i--; i&=i+1) 
			a+=f[i].first, b+=f[i].second;
		return a*T(pos) - b;
	}
};