一次修改不是最多产生 O(log) 个新 tag 吗

为什么我这么写会 mle

#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;

using ll = long long;
constexpr int N = 3e5 + 5, P = 1e9 + 9;

int n, m, a[N];
ll s[N];

struct Node {
	vector<pair<int, int>> tag;
	ll sum;
	void addtag(int l, int r) {
		sum = (sum + s[r] - s[l - 1]) % P;
		if(sum < 0) {
			sum += P;
		}
		tag.eb(l, r);
	}
} t[N << 2];

#define ls x << 1
#define rs ls | 1
void pushup(int x) {
	t[x].sum = (t[ls].sum + t[rs].sum) % P;
}
void pushdown(int x) {
	if(!t[x].tag.empty()) {
		for(auto [l, r] : t[x].tag) {
			int mid = l + r >> 1;
			t[ls].addtag(l, mid);
			t[rs].addtag(mid + 1, r);
		}
		t[x].tag.clear();
	}
}
void build(int x = 1, int l = 1, int r = n) {
	if(l == r) {
		cin >> t[x].sum;
		return;
	}
	int mid = l + r >> 1;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	pushup(x);
}
void add(int L, int R, int x = 1, int l = 1, int r = n) {
	if(L <= l && r <= R) {
		t[x].addtag(l - L + 1, r - L + 1);
		return;
	}
	pushdown(x);
	int mid = l + r >> 1;
	if(L <= mid) add(L, R, ls, l, mid);
	if(R > mid) add(L, R, rs, mid + 1, r);
	pushup(x);
}
int query(int L, int R, int x = 1, int l = 1, int r = n) {
	if(L <= l && r <= R) {
		return t[x].sum;
	}
	pushdown(x);
	int mid = l + r >> 1;
	int ret = 0;
	if(L <= mid) ret = query(L, R, ls, l, mid);
	if(R > mid) ret = (ret + query(L, R, rs, mid + 1, r)) % P;
	return ret;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	s[1] = s[2] = 1;
	for(int i = 3; i <= n; ++ i) {
		s[i] = (s[i - 1] + s[i - 2]) % P;
	}
	for(int i = 1; i <= n; ++ i) {
		s[i] = (s[i - 1] + s[i]) % P;
	}
	build();
	while(m --) {
		int op, l, r;
		cin >> op >> l >> r;
		if(op == 1) {
			add(l, r);
		}
		else {
			cout << query(l, r) << '\n';
		}
	}
	return 0;
}