Line Tree Advance

Line Tree Advance

imperfect!!!!!!

Line Tree Boards.

#define lc u<<1
#define rc u<<1|1
const int N = 200005;
struct tree{
	int l,r,su,tag;
}tr[N << 2];
void push_up(tree &u,tree l,tree r){
}
void build(int u,int l,int r){
	tr[u] = {l,r,a[l],0};
	if(l==r) return;
	int mid = l+r>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	push_up(tr[u],tr[lc],tr[rc]);
}
void calc(int u,int op){
	tree& t = tr[u];
	if(op==1){
        
	}else{
        
	}
}
void push_down(int u){
	if(tr[u].tag == ?) calc(lc,?),calc(rc,?);
	if(tr[u].tag == ?) calc(lc,?),calc(rc,?);
    
	tr[u].tag = 0;
}
void update(int u,int l,int r,int op){
	if(tr[u].l > r || tr[u].r < l) return;
	if(tr[u].l >= l && tr[u].r <= r){
		calc(u,op);
		return;
	}
	push_down(u);
    if(l > tr[lc].r){
		update(rc,l,r,op);
		push_up(tr[u],tr[lc],tr[rc]);
		return;
	}
	if(r < tr[rc].l){
		update(lc,l,r,op);
		push_up(tr[u],tr[lc],tr[rc]);
		return;
	}
	update(lc,l,r,op);
	update(rc,l,r,op);
	push_up(tr[u],tr[lc],tr[rc]);
}
//Consolidated query
T quary(int u,int l,int r){
	if(tr[u].l > r || tr[u].r < l) return {} ;
	if(tr[u].l >= l && tr[u].r <= r){
		return tr[u];
	}
	push_down(u);
	if(l > tr[lc].r) return quary(rc,l,r); //In the right half
	if(r < tr[rc].l) return quary(lc,l,r); //In the left half
	T t;
	push_up(t,quary(lc,l,r),quary(rc,l,r));//A little of each.
	return t;
}

Line Tree + Greedy / Line Tree + Sorting

Example.

1. Rock Valley P1607 Fair Shuttle G

Link.

[P1607 USACO09FEB] Fair Shuttle G - Rock Valley | The New Ecology of Computer Science Education ()

Thoughts.

Line covering greedy problem, observation and comparison found that according to the r chronological order of the answer is significantly larger, to maintain the maximum value of the interval can be, pay attention to do the modification operation, because in the middle of the cow on the car will affect the maximum value of the

Code.

#define lc u<<1
#define rc u<<1|1
const int N = 20005;
struct node
{
	int l,r,w;
	bool operator<(const node &n1)const{
		return r < ;
	}; 
};
struct tree{
	int l,r,mx,add;
}tr[N << 2];
void push_up(int u){
	tr[u].mx = max(tr[lc].mx,tr[rc].mx);
}
void push_down(int u){
	tr[lc].add += tr[u].add;
	tr[rc].add += tr[u].add;
	tr[lc].mx += tr[u].add;
	tr[rc].mx += tr[u].add;
	tr[u].add = 0;
}
void build(int u,int l,int r){
	tr[u] = {l,r,0,0};
	if(l==r) return;
	int mid = l + r >> 1;
	build(lc,l,mid);
	build(rc,mid + 1,r);
}
void update(int u,int l,int r,int v){
	if(tr[u].l > r || tr[u].r < l) return;
	if(tr[u].l >= l && tr[u].r <= r){
		tr[u].mx += v;
		tr[u].add += v;
		return;
	}
	push_down(u);
	update(lc,l,r,v);
	update(rc,l,r,v);
	push_up(u);
}
int quary(int u,int l,int r){
	if(tr[u].l > r || tr[u].r < l) return 0;
	if(tr[u].l >= l && tr[u].r <= r){
		return tr[u].mx;
	}
	push_down(u);
	return max(quary(lc,l,r),quary(rc,l,r));
}
int n,m,c;
vector<node> a;
void solve(){
	cin >> n >> m >> c;
	build(1,1,m + 1);
	for(int i = 1;i<=n;i++){
		int l,r,w;
		cin >> l >> r >> w;
		a.push_back({l,r,w});
	}
	sort((),());

	int ans = 0;
	for(int i = 0;i < n;i++){
		int l = a[i].l, r= a[i].r, w = a[i].w; 
		int mx = quary(1,l,r - 1);
		int on = min(c - mx,w);
		ans+=on;
		update(1,l,r - 1,on);
	}
	cout << ans << endl;
}

2. Rock Valley P1937 Barn Allocation G

Link.

[P1937 USACO10MAR] Barn Allocation G - Rock Valley | The New Ecology of Computer Science Education ()

Thoughts.

Line covering greedy problem, observation and comparison found that the answer obtained by r time order is significantly better, the beginning of the array to build a line tree, indicating the current capacity of the minimum value of each interval, to determine whether a cow can be added to an interval, to join, then ans + +, at the same time updating the interval will be the capacity of the interval - 1;.

Code.

#define lc u<<1
#define rc u<<1|1
const int N = 100005;
int a[N];
struct node{
	int l,r;
	bool operator<(const node & n1) const{
		return r < ;
	}
};
struct tree{
	int l,r,mi,add;
}tr[N << 2];
void push_up(int u){
	tr[u].mi = min(tr[lc].mi,tr[rc].mi);
}
void push_down(int u){
	tr[lc].add += tr[u].add;
	tr[rc].add += tr[u].add;
	tr[lc].mi -= tr[u].add;
	tr[rc].mi -= tr[u].add;
	tr[u].add = 0;
}
void build(int u,int l,int r){
	tr[u] = {l,r,0x3f3f3f3f,0};
	if(l==r){
		tr[u] = {l,r,a[l],0};
		return; 
	}
	int mid = l + r >> 1;
	build(lc,l,mid);
	build(rc,mid + 1,r);
	push_up(u);
}
void update(int u,int l,int r,int v){
	if(tr[u].l > r || tr[u].r < l) return;
	if(tr[u].l >= l && tr[u].r <= r){
		tr[u].mi -= v;
		tr[u].add += v;
		return;
	}
	push_down(u);
	update(lc,l,r,v);
	update(rc,l,r,v);
	push_up(u);
}
int quary(int u,int l,int r){
	if(tr[u].l > r || tr[u].r < l) return 0x3f3f3f3f;
	if(tr[u].l >= l && tr[u].r <= r){
		return tr[u].mi;
	}
	push_down(u);
	return min(quary(lc,l,r),quary(rc,l,r));
}
int n,m;
void solve(){
	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
	}
	build(1,1,n);
	vector<node> a;
	for(int i = 1;i<=m;i++){
		int l,r;
		cin >>l >> r;
		a.push_back({l,r});
	}
	sort((),());
	int ans = 0;
	for(int i = 0; i < m;i++){
		int l = a[i].l, r = a[i].r;
		int mi = quary(1,l,r);
		if(mi <= 0){
			continue;
		}
		ans++;
		update(1,l,r,1);
	}
	cout << ans << endl;
}

3. Necklace from P1972 HH, Rock Valley

Link.

[P1972 SDOI2009] HH's Necklace - Rock Valley | New Ecology of Computer Science Education ()

Thoughts.

We will change the online inquiry to offline, and then sort r, and then sequentially traverse the array, if encountered before the number of occurrences, the last occurrence of the previous subscript, a single point of modification -1, the current subscript +1, for each r to open a bucket, and then the line tree statistics can be answer

Code.

#define lc u<<1
#define rc u<<1|1
const int N = 1000005;
struct node{
	int l,r,id;
	bool operator<(const node & n1) const{
		return r  < ;
	}
};
struct tree{
	int l,r,su;
}tr[N << 2];
void push_up(int u){
	tr[u].su = tr[lc].su+tr[rc].su;
}
void build(int u,int l,int r){
	tr[u] = {l,r,0};
	if(l==r) return;
	int mid = l + r >> 1;
	build(lc,l,mid);
	build(rc,mid + 1,r);
}
void update(int u,int x,int v){
	if(tr[u].l > x || tr[u].r < x) return;
	if(tr[u].l == x && tr[u].r == x){
		tr[u].su += v;
		return;
	}
	update(lc,x,v);
	update(rc,x,v);
	push_up(u);
}
int quary(int u,int l,int r){
	if(tr[u].l > r || tr[u].r < l) return 0;
	if(tr[u].l >= l && tr[u].r <= r){
		return tr[u].su;
	}
	return quary(lc,l,r) + quary(rc,l,r);
}
int n,m;
int a[N],last[N],ans[N];
vector<node> v[N];
vector<node> qs;
void solve(){
	cin >> n;
	build(1,1,n);
	for(int i = 1;i<=n;i++){
		cin >> a[i];
	}
	cin >> m;
	for(int i = 1; i <= m;i++){
		int l,r;
		cin >> l >> r;
		v[r].push_back({l,r,i});
		sort(v[r].begin(),v[r].end());
	}
	for(int i = 1;i<=n;i++){
		if(last[a[i]]){
			update(1,last[a[i]],-1);
		}
		last[a[i]] = i;
		update(1,i,1);
		for(auto &p:v[i]){
			ans[] = quary(1,,);
		}
	}
	for(int i =1;i<=m;i++){
		cout << ans[i] << endl;
	}
}

Line Tree + Double Pointer

Example.

1. Rock Valley P1712 Interval

Link.

[P1712 NOI2016] Interdistrict - Rock Valley | The New Ecology of Computer Science Education ()/problem/P1937)

Thoughts.

Record each interval and sorted by the length of the interval, the same direction double pointer, to see whether there is a length of the array interval (that is, the maximum length, more than m, there is the right pointer does not move, the left pointer continues to move to the right, to update the answer to the minimum value)

Code.

#define lc u<<1
#define rc u<<1|1
const int N = 500005;
struct node{
	int l,r,len;
	bool operator<(const node & n1) const{
		return len  < ;
	}
};
struct tree{
	int l,r,ma,add;
}tr[N*2 << 2];
void push_up(int u){
	tr[u].ma = max(tr[lc].ma,tr[rc].ma);
}
void push_down(int u){
	tr[lc].add += tr[u].add;
	tr[rc].add += tr[u].add;
	tr[lc].ma += tr[u].add;
	tr[rc].ma += tr[u].add;
	tr[u].add = 0;
}
void build(int u,int l,int r){
	tr[u] = {l,r,0,0};
	if(l==r) return;
	int mid = l + r >> 1;
	build(lc,l,mid);
	build(rc,mid + 1,r);
	push_up(u);
}
void update(int u,int l,int r,int v){
	if(tr[u].l > r || tr[u].r < l) return;
	if(tr[u].l >= l && tr[u].r <= r){
		tr[u].ma += v;
		tr[u].add += v;
		return;
	}
	push_down(u);
	update(lc,l,r,v);
	update(rc,l,r,v);
	push_up(u);
}
int quary(int u,int l,int r){
	if(tr[u].l > r || tr[u].r < l) return 0;
	if(tr[u].l >= l && tr[u].r <= r){
		return tr[u].ma;
	}
	push_down(u);
	return max(quary(lc,l,r),quary(rc,l,r));
}
int n,m;
void solve(){
	cin >> n >> m;
	vector<node> a;
	vector<int> v;
	for(int i = 1;i<=n;i++){
		int l,r;
		cin >>l >> r;
		a.push_back({l,r,r-l});
		v.push_back(l);
		v.push_back(r);
	}
	sort((),());
	(unique((),()),());
	int sz = ();
	sort((),());
	build(1,1,2*n);
	for(int i = 0;i < n;i++){
		a[i].l = lower_bound((),(),a[i].l) - () + 1;
		a[i].r = lower_bound((),(),a[i].r) - () + 1;
	}
	
	int j = 0;
	int ans = 0x3f3f3f3f;
	for(int i = 0;i < n;i++){
		int l = a[i].l,r = a[i].r;
		update(1,l,r,1);
		while(j <= i && tr[1].ma == m){
			update(1,a[j].l,a[j].r,-1);
			ans=min(ans,a[i].len - a[j].len);
			j++;
		}
	}
	if(ans==0x3f3f3f3f){
		cout << -1 <<endl;
		return;
	}
	cout << ans << endl;
}

Line Tree + Multiple Marker Maintenance

Example.

1. Rock Valley P2572 Sequence Operation

Link.

[P2572 SCOI2010] Sequence Operations - Rock Valley | New Ecology of Computer Science Education ()

Thoughts.

Maintain 2 lazy tags, and multiple normal tags, and add not only 1's but also 0's to facilitate changes after inversion.

Consider updating lazy, the priority is definitely the override operation, then the reversal.

Code.

#define lc u<<1
#define rc u<<1|1
int a[N];
struct tree{
	int l,r;
	int s0,l0,r0,m0; //0ordinal number,longest left,right-hand side,total maximum length
	int s1,l1,r1,m1; //1ordinal number,longest left,right-hand side,total maximum length
	int len;
	int rev,tag; //rev 0/1Whether to invert, tag -1unmarked/ 0comprise0 / 1comprise1
}tr[N<<2];
void push_up(tree& t,tree p1,tree p2){
	t.s0 = p1.s0 + p2.s0;
	t.l0 = p1.s1 ? p1.l0 : p1.s0 + p2.l0;
	t.r0 = p2.s1 ? p2.r0 : p2.s0 + p1.r0;
	t.m0 = max(p1.r0 + p2.l0,max(p1.m0,p2.m0));

	t.s1 = p1.s1 + p2.s1;
	t.l1 = p1.s0 ? p1.l1 : p1.s1 + p2.l1;
	t.r1 = p2.s0 ? p2.r1 : p2.s1 + p1.r1;
	t.m1 = max(p1.r1 + p2.l1,max(p1.m1,p2.m1));
}
void calc(int u,int op){
	tree& t = tr[u];
	if(op==0){
		t.s0 = t.l0 = t.r0 = t.m0 = ;
		t.s1 = t.l1 = t.r1 = t.m1 = 0;
		=0;
		=0;
	}
	if(op==1){
		t.s0 = t.l0 = t.r0 = t.m0 = 0;
		t.s1 = t.l1 = t.r1 = t.m1 = ;
		=1;
		=0;
	}
	if(op==2){
		swap(t.s0,t.s1);
		swap(t.l0,t.l1);
		swap(t.r0,t.r1);
		swap(t.m0,t.m1);
		^=1;
	}
}
void push_down(int u){
	tree& t = tr[u];
	if(==0) calc(lc,0),calc(rc,0);
	if(==1) calc(lc,1),calc(rc,1);
	if() calc(lc,2),calc(rc,2);
	 = -1; = 0;
}
void build(int u,int l,int r){
	int t = a[l];
	//If it ist=0 t^1 = 1; 0 ordinal number it just so happens that1,1ordinal numberit just so happens that0,The other way around makes sense.
	tr[u] = {l,r,t^1,t^1,t^1,t^1,t,t,t,t,r-l+1,0,-1};
	if(l==r) return;
	int mid = l+r>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	push_up(tr[u],tr[lc],tr[rc]);
}
void update(int u,int l,int r,int op){
	if(tr[u].l > r || tr[u].r < l) return;
	if(tr[u].l >= l && tr[u].r <= r){
		calc(u,op);
		return;
	}
	push_down(u);
	update(lc,l,r,op);
	update(rc,l,r,op);
	push_up(tr[u],tr[lc],tr[rc]);
}
tree qy(int u,int l,int r){
	if(tr[u].l > r || tr[u].r < l) return { };
	if(tr[u].l >= l && tr[u].r <= r){
		return tr[u];
	}
	push_down(u);
	tree ne;
	push_up(ne,qy(lc,l,r),qy(rc,l,r));
	return ne;
}
void solve(){
	int n,m;
	cin >> n >> m;
	for(int i = 1;i<=n;i++) cin >>a[i];
	build(1,1,n);
	for(int i = 1;i<=m;i++){
		int op,l,r;
		cin >> op>>l>>r;
		++l,++r;
		if(op<3){
			update(1,l,r,op);
		}else if(op==3){
			tree ne = qy(1,l,r);
			printf("%d\n",ne.s1);
		}else if(op==4){
			tree ne = qy(1,l,r);
			printf("%d\n",ne.m1);
		}
	}
}

Line Tree + Bisection

Example.

1. Rock Valley P4344 Brain Cave Therapeutic Instrument

Link.

[P4344 SHOI2015] Brain Cave Therapeutic Apparatus - Rock Valley | New Ecology of Computer Science Education ()

Thoughts.

We maintain the length of the longest consecutive 0's, maintain the number of 1's, and then we bisect the region to be filled into the smallest legal region.\([l,x](x is the right boundary of our bisection)\)Note the details of the code when merging the lengths at the end of the quary, which is commented.

Code.

#define lc u<<1
#define rc u<<1|1
int n,m;
struct tree{
	int l,r,len,s1,l1,r1,m1,tag;
}tr[N<<2];
void push_up(tree &u,tree l,tree r){
	u.s1 = l.s1+r.s1;
	u.l1 = l.s1 ? l.l1 :+r.l1 ;
	u.r1 = r.s1 ? r.r1 : l.r1+ ;
	u.m1 = max(max(l.m1,r.m1),l.r1+r.l1);
}
void build(int u,int l,int r){
	tr[u] = {l,r,r-l+1,1,0,0,0,-1};
	if(l==r) return;
	int mid = l+r>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	push_up(tr[u],tr[lc],tr[rc]);
}
void calc(int u,int op){
	tree& t = tr[u];
	if(op==1){
		t.s1 = ;
		t.l1 = t.r1 = t.m1 = 0;
		 = 1;
	}else{
		t.s1 = 0;
		t.l1 = t.r1 = t.m1 = ;
		 = 0;
	}
}
void push_down(int u){
	if(tr[u].tag == 1) calc(lc,1),calc(rc,1);
	if(tr[u].tag == 0) calc(lc,0),calc(rc,0);
	tr[u].tag = -1;
}
//There are only two operations,one-pointed0,always be in the right place1
void update(int u,int l,int r,int op){
	if(tr[u].l > r || tr[u].r < l) return;
	if(tr[u].l >= l && tr[u].r <= r){
		calc(u,op);
		return;
	}
	push_down(u);
	update(lc,l,r,op);
	update(rc,l,r,op);
	push_up(tr[u],tr[lc],tr[rc]);
}
int q1(int u,int l,int r){
	if(tr[u].l > r || tr[u].r < l) return 0;
	if(tr[u].l >= l && tr[u].r <= r){
		return tr[u].s1;
	}
	push_down(u);
	return q1(lc,l,r)+q1(rc,l,r);
}
int q0(int u,int l,int r){
	if(tr[u].l > r || tr[u].r < l) return 0;
	if(tr[u].l >= l && tr[u].r <= r){
		return tr[u].len - tr[u].s1;
	}
	push_down(u);
	return q0(lc,l,r)+q0(rc,l,r);
}
void work(int l0,int r0,int l1,int r1){
	int x = q1(1,l0,r0);
	update(1,l0,r0,0);
	if(x==0) return;
	int l = l1,r = r1,ans = -1;
	while(l<=r){
		int mid = l+r>>1;
		if(q0(1,l1,mid) <= x){
			l = mid + 1;
			ans = mid;
		}else{
			r = mid - 1;
		}
	}
	if(ans==-1) return;
	update(1,l1,ans,1);
}
tree quary(int u,int l,int r){
	if(tr[u].l > r || tr[u].r < l) return { } ;
	if(tr[u].l >= l && tr[u].r <= r){
		return tr[u];
	}
	push_down(u);
	if(l > tr[lc].r) return quary(rc,l,r); //In the right half
	if(r < tr[rc].l) return quary(lc,l,r); //In the left half
	tree t;
	push_up(t,quary(lc,l,r),quary(rc,l,r));//A little of each.
	return t;
}
void solve(){
	cin >> n >> m;
	build(1,1,n);
	while(m--){
		int op,l,r;
		cin >> op >> l >> r;
		if(op==0) update(1,l,r,0);
		if(op==1){
			int l1,r1;
			cin>>l1>>r1;
			work(l,r,l1,r1);
		}
		if(op==2){
			cout << quary(1,l,r).m1 << endl;
		}
	}
}

2. Rock Valley P2824 Sort

Link.

[P2824 HEOI2016/TJOI2016] Sort - Rock Valley | The New Ecology of Computer Science Education ()

Thoughts.

Because it is arranged, we think of dichotomous answers, for a hypothetical answer x set >= x number equal to 1, less than or equal to the number of x is 0, then the construction of the line tree, can be extremely fast solution to the sorting, the problem and then every time check out the topic requires idx position is 1 then the left pointer right, why? Because x can be satisfied, then 1 ~ x-1 can be satisfied, so we interval to go x +1 ~ r in trying to find the answer

Code.

#define lc u<<1
#define rc u<<1|1
int n,m;
struct qs{
	int op,l,r;
}q[N];
//We'll split the number two ways.,See if the operation is completedidxThis position.=1;
int a[N];
struct tree{
	int l,r,su,len,tag;
}tr[N<<2];
void push_up(int u){
	tr[u].su = tr[lc].su + tr[rc].su;
}
void build(int u,int l,int r,int x){
	tr[u] = {l,r,(a[l]>=x),r-l+1,-1};
	if(l==r)return;
	int mid = (l + r) >>1;
	build(lc,l,mid,x);
	build(rc,mid+1,r,x);
	push_up(u);
}
void calc(int u,int op){
	if(op==0){
		tr[u].su = 0;
	}else{
		tr[u].su = tr[u].len;
	}
	tr[u].tag = op;
}
void push_down(int u){
	if(tr[u].tag==0) calc(lc,0),calc(rc,0);
	if(tr[u].tag==1) calc(lc,1),calc(rc,1);
	tr[u].tag = -1;
}
void update(int u,int l,int r,int op){
	if(tr[u].l > r || tr[u].r < l) return;
	if(tr[u].l >= l && tr[u].r <= r){
		calc(u,op);
		return;
	}
	push_down(u);
	update(lc,l,r,op);
	update(rc,l,r,op);
	push_up(u);
}
int q1(int u,int l,int r){
	if(tr[u].l > r || tr[u].r < l) return 0;
	if(tr[u].l>=l&&tr[u].r<=r){
		return tr[u].su;
	}
	push_down(u);
	return q1(lc,l,r) + q1(rc,l,r);
}

int idx;
bool check(int x){
	build(1,1,n,x);
	for(int i = 1;i <= m;i++){
		int op = q[i].op,l = q[i].l,r = q[i].r;
		if(op==1){
			int cnt = r - l + 1;
			int su = q1(1,l,r);
			update(1,l,l + su - 1,1);
			update(1,l + su,r,0);
		}else{
			int cnt = r - l + 1;
			int su = q1(1,l,r);
			update(1,l,r - su,0);
			update(1,r - su + 1,r,1);
		}
	}
	return q1(1,idx,idx)==1;
}
void work(){
	int l = 1,r = n,ans = -1;
	while(l<=r){
		int mid = l + r >> 1;
		if(check(mid)){
			l = mid + 1;
			ans = mid;
		}else{
			r = mid - 1;
		}
	}
	cout << ans << endl;
}
void solve(){
	cin >> n >> m;
	for(int i =1;i<=n;i++) cin >> a[i];
	for(int i = 1;i<=m;i++){
		cin >> q[i].op >> q[i].l >> q[i].r;
	}
	cin >> idx;
	work();
}

Line Tree + Math

Example.

1. Logu P5142 Variance

Link.

P5142 Interval Variance - Rock Valley | The New Ecology of Computer Science Education ()/problem/P4344)

Thoughts.

Question:Ask for the variance of an interval\(\frac{1}{n}\sum_{i=1}^n(a_i - a)^2\) where a is the interval mean\(a = \frac{1}{n}\sum_{i=1}^{n}a_i\)
We simplify the formula For ease of viewing, we set the interval mean to\(b\)
\(d = \frac{1}{n}\sum_{i = 1}^n(a_i - b)^2\)
\(=\frac{1}{n}\sum_{i = 1}^n(a_i^2 - 2a_ib + b^2)\)
\(=\frac{1}{n}(\sum_{i = 1}^na_i^2 - \sum_{i = 1}^n2a_ib +\sum_{i = 1}^n b^2)\)
\(=\frac{1}{n}(\sum_{i = 1}^na_i^2 - 2b\sum_{i = 1}^na_i +n b^2)\)
\(=\frac{1}{n}(\sum_{i = 1}^na_i^2 - 2bnb +nb^2)\)
\(=\frac{1}{n}(\sum_{i = 1}^na_i^2 - 2nb^2 +nb^2)\)
\(=\frac{1}{n}(\sum_{i = 1}^na_i^2 - nb^2)\)
\(=\frac{1}{n}\sum_{i = 1}^na_i^2 - b^2\)

It is sufficient for the line tree to maintain interval sums and interval squares

Code.

#define lc u<<1
#define rc u<<1|1
const int N = 200005;
const int MOD = 1e9+7;
int n,m;
int b[N];
struct tree{
	int l,r,s1,s2;
}tr[N<<2];
void push_up(int u){
	tr[u].s1 = (tr[lc].s1 + tr[rc].s1)%MOD;
	tr[u].s2 = (tr[lc].s2 + tr[rc].s2)%MOD;
}
void build(int u,int l,int r){
	tr[u] = {l,r,b[l],b[l]*b[l]%MOD};
	if(l==r) return;
	int mid = l+r>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	push_up(u);
}
void update(int u,int x,int v){
	if(tr[u].l > x || tr[u].r < x) return;
	if(tr[u].l==x&&tr[u].r==x){
		tr[u].s1 = v;
		tr[u].s2 = (v*v)%MOD;
		return;
	}
	update(lc,x,v);
	update(rc,x,v);
	push_up(u);
}
int q1(int u,int l,int r){
	if(tr[u].l > r || tr[u].r < l) return 0;
	if(tr[u].l>=l&&tr[u].r<=r){
		return tr[u].s1;
	}
	return (q1(lc,l,r) + q1(rc,l,r))%MOD;
}
int q2(int u,int l,int r){
	if(tr[u].l > r || tr[u].r < l) return 0;
	if(tr[u].l>=l&&tr[u].r<=r){
		return tr[u].s2;
	}
	return (q2(lc,l,r) + q2(rc,l,r))%MOD;
}
int ksm(int x,int n){
	int res = 1;
	while(n){
		if(n&1) res = res * x % MOD;
		x = x*x%MOD;
		n>>=1;
	}
	return res;
}
void solve(){
	cin >> n >> m;
	for(int i = 1;i<=n;i++) cin >> b[i];
	build(1,1,n);
	while(m--){
		int op,l,r;
		cin >> op >> l >> r;
		if(op==1){
			update(1,l,r);
		}else{
			int s1 = q1(1,l,r);
			int s2 = q2(1,l,r);
			int len = r-l+1;
			int iv = ksm(len,MOD-2)%MOD;
			s2 = s2*iv%MOD;
			s1 = s1*iv%MOD;
			s1 = (s1*s1)%MOD;
			int res = ((s2 - s1)%MOD + MOD)%MOD;
			cout << res <<endl;  
		}	
	}
}