Segment Tree Template

struct node {
    int idx, lazy, lhs, rhs;
    node (int idx = 0, int lhs = 0, int rhs = 0) : idx (idx), lhs (lhs), rhs (rhs) {
        // lazy সেট করা নেই, করে নিতে হবে, সাথে অন্যান্য value গুলাও
        // normal single node আর temp (identity) যদি একই ভাবে init করা না যায় তাহলে if (lhs == rhs && idx) {
        // temp কে তখন আলাদা ভাবে init করে নিতে হবে
        if (lhs == rhs) {
        } else {
        }
    }

    bool operator < (const node &temp) const {}
    friend ostream &operator << (ostream &ostr, node &temp) {
        ostr << "{" << temp.lazy << ", " << ", " << temp.lhs << ", " << temp.rhs << "}";
        return ostr;
    }

    void normalize (int addLazy) { /* normalize মানে current node এর lazy এর সাথে শুধু নতুন lazy (addLazy) যোগ করা  */ }
    void modify (node &le, node &ri) { /* left child আর right child থেকে current node এর value গুলা সেট করতে হবে */ }
    void split ();
    void merge ();
} tree [MAX_N << 2];

void node :: split () {
    if (!lazy) return;
    // lazy অনুসারে এইখানে current node এর value গুলা সেট করতে হবে, lazy তখন 0 হয়ে যাবে

    if (lhs == rhs) { lazy = 0; return; }
    tree [idx << 1].normalize (lazy);
    tree [idx << 1 | 1].normalize (lazy);
    lazy = 0;
}

void node :: merge () {
    tree [idx << 1].split ();
    tree [idx << 1 | 1].split ();
    modify (tree [idx << 1], tree [idx << 1 | 1]);
}

void build (int idx, int lhs, int rhs) {
    tree [idx] = node (idx, lhs, rhs);
    if (lhs == rhs) return;

    int mid = (lhs + rhs) >> 1;
    build (idx << 1, lhs, mid);
    build (idx << 1 | 1, mid + 1, rhs);
    tree [idx].merge ();
}

node query (node &cur, int qLhs, int qRhs) {
    int mid = (cur.lhs + cur.rhs) >> 1;
    node temp, right;
    cur.split ();

    if (qLhs <= cur.lhs && cur.rhs <= qRhs) return cur;
    if (qLhs <= mid) temp = query (tree [cur.idx << 1], qLhs, qRhs);
    if (qRhs > mid) { right = query (tree [cur.idx << 1 | 1], qLhs, qRhs); temp.modify (temp, right); }
    return temp;
}

void update (node &cur, int uLhs, int uRhs, int lazy) {
    int mid = (cur.lhs + cur.rhs) >> 1;
    if (uLhs <= cur.lhs && cur.rhs <= uRhs) {
        cur.normalize (lazy);
        cur.split ();
        return;
    }

    cur.split ();
    if (uLhs <= mid) update (tree [cur.idx << 1], uLhs, uRhs, lazy);
    if (uRhs > mid) update (tree [cur.idx << 1 | 1], uLhs, uRhs, lazy);
    cur.merge ();
}

void build  (int n) { build (1, 1, n); }
node query  (int qLhs, int qRhs) { return query (tree [1], qLhs, qRhs); }
void update (int pos, int val) { update (tree [1], pos, pos, val); }
void update (int uLhs, int uRhs, int lazy) { update (tree [1], uLhs, uRhs, lazy); }