broken segment tree lazy propagation

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;



const int mod = 1e9 + 9;
const int maxn = 300005;

int n;
int a[maxn];
ll tree[3*maxn], lazy[3*maxn];

void updateRange(int k, int x, int y, int a, int b, int v) {
    if (lazy[k] != 0) {
        // lazy propagation
        tree[k] += ll(y - x + 1) * lazy[k];
        tree[k] %= mod;
        if (x != y) {
            lazy[2*k] += lazy[k];
            lazy[2*k] %= mod;
            lazy[2*k+1] += lazy[k];
            lazy[2*k+1] %= mod;
        }
        lazy[k] = 0;
    }
    if (x > b || y < a) {
        // completely out of range
        return;
    }
    if (a <= x && y <= b) {
        // completely in range
        tree[k] += ll(y - x + 1) * v;
        tree[k] %= mod;
        if (x != y) {
            lazy[2*k] += v;
            lazy[2*k+1] += v;
        }
    } else {
        // partially in range
        int d = (x + y) / 2;
        updateRange(2*k, x, d, a, b, v);
        updateRange(2*k+1, d+1, y, a, b, v);
        tree[k] = (tree[2*k] + tree[2*k+1]) % mod;
    }
}

ll sumRange(int k, int x, int y, int a, int b) {
    if (x > b || y < a) {
        // completely out of range
        return 0;
    }
    if (lazy[k] != 0) {
        // lazy propagation
        tree[k] += ll(y - x + 1) * lazy[k];
        if (x != y) {
            lazy[2*k] += lazy[k];
            lazy[2*k] %= mod;
            lazy[2*k+1] += lazy[k];
            lazy[2*k+1] %= mod;
        }
        lazy[k] = 0;
    }
    if (a <= x && y <= b) {
        // completely in range
        return tree[k];
    } else {
        int d = (x + y) / 2;
        return (sumRange(2*k, x, d, a, b) + sumRange(2*k+1, d+1, y, a, b)) % mod;
    }
}

void Main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    while (true) {
        int t, l, r;
        cin >> t >> l >> r;
        --l, --r;
        if (t == 1) {
            int x;
            cin >> x;
            updateRange(1, 0, n-1, l, r, x);
        } else {
            int ans = sumRange(1, 0, n-1, l, r);
            cout << ans << '\n';
        }
    }
}

int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(0);
    #ifndef _DEBUG
    #endif
    Main();
    return 0;
}