# 线段树

{% hint style="success" %}
[洛谷 P3372 【模板】线段树 1](https://www.luogu.com.cn/problem/P3372)
{% endhint %}

```cpp
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using p = pair<int, int>;
const int maxn(1e5 + 10);

struct node {
    int l, r;
    ll sum, lz;
} tree[maxn << 2];

template<typename T = int>
inline const T read()
{
    T x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

template<typename T>
inline void write(T x, bool ln)
{
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10, false);
    putchar(x % 10 + '0');
    if (ln) putchar(10);
}

inline int ls(int cur)
{
    return cur << 1;
}

inline int rs(int cur)
{
    return cur << 1 | 1;
}

void push_up(int cur)
{
    tree[cur].sum = tree[ls(cur)].sum + tree[rs(cur)].sum;
}

void push_down(int cur)
{
    if (tree[cur].lz) {
        tree[ls(cur)].sum += (tree[ls(cur)].r - tree[ls(cur)].l + 1) * tree[cur].lz;
        tree[rs(cur)].sum += (tree[rs(cur)].r - tree[rs(cur)].l + 1) * tree[cur].lz;
        tree[ls(cur)].lz += tree[cur].lz;
        tree[rs(cur)].lz += tree[cur].lz;
        tree[cur].lz = 0;
    }
}

void build(int cur, int l, int r)
{
    tree[cur].l = l;
    tree[cur].r = r;
    tree[cur].lz = 0;
    if (l == r) {
        tree[cur].sum = read();
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(cur), l, mid);
    build(rs(cur), mid + 1, r);
    push_up(cur);
}

void update(int cur, int l, int r, int v)
{
    if (tree[cur].l == l and tree[cur].r == r) {
        tree[cur].sum += (r - l + 1) * v;
        tree[cur].lz += v;
        return;
    }
    push_down(cur);
    int mid = (tree[cur].l + tree[cur].r) >> 1;
    if (r <= mid) {
        update(ls(cur), l, r, v);
    } else if (l > mid) {
        update(rs(cur), l, r, v);
    } else {
        update(ls(cur), l, mid, v);
        update(rs(cur), mid + 1, r, v);
    }
    push_up(cur);
}

ll query(int cur, int l, int r)
{
    if (tree[cur].l == l and tree[cur].r == r) {
        return tree[cur].sum;
    }
    push_down(cur);
    int mid = (tree[cur].l + tree[cur].r) >> 1;
    if (r <= mid) return query(ls(cur), l, r);
    if (l > mid) return query(rs(cur), l, r);
    return query(ls(cur), l, mid) + query(rs(cur), mid + 1, r);
}

int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("input.txt", "r", stdin);
#endif
    int n = read(), m = read();
    build(1, 1, n);
    while (m--) {
        int t = read(), x = read(), y = read();
        if (t == 1) {
            int k = read();
            update(1, x, y, k);
        } else {
            write(query(1, x, y), true);
        }
    }
    return 0;
}
```

{% hint style="success" %}
[洛谷 P3373 【模板】线段树 2](https://www.luogu.com.cn/problem/P3373)
{% endhint %}

```cpp
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using p = pair<int, int>;
const int maxn(1e5 + 10);
int mod;

struct {
    int l, r;
    ll val, add, mult;
} tree[maxn << 2];

template<typename T = int>
inline const T read()
{
    T x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

template<typename T>
inline void write(T x, bool ln)
{
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10, false);
    putchar(x % 10 + '0');
    if (ln) putchar(10);
}

inline int ls(int cur)
{
    return cur << 1;
}

inline int rs(int cur)
{
    return cur << 1 | 1;
}

void push_up(int cur)
{
    tree[cur].val = (tree[ls(cur)].val + tree[rs(cur)].val) % mod;
}

void push_down(int cur)
{
    if (tree[cur].add or tree[cur].mult not_eq 1) {
        tree[ls(cur)].val = ((tree[ls(cur)]).val * tree[cur].mult + (tree[ls(cur)].r - tree[ls(cur)].l + 1) * tree[cur].add) % mod;
        tree[rs(cur)].val = ((tree[rs(cur)]).val * tree[cur].mult + (tree[rs(cur)].r - tree[rs(cur)].l + 1) * tree[cur].add) % mod;
        tree[ls(cur)].mult = tree[ls(cur)].mult * tree[cur].mult % mod;
        tree[rs(cur)].mult = tree[rs(cur)].mult * tree[cur].mult % mod;
        tree[ls(cur)].add = (tree[ls(cur)].add * tree[cur].mult + tree[cur].add) % mod;
        tree[rs(cur)].add = (tree[rs(cur)].add * tree[cur].mult + tree[cur].add) % mod;
        tree[cur].add = 0;
        tree[cur].mult = 1;
    }
}

void build(int cur, int l, int r)
{
    tree[cur].l = l;
    tree[cur].r = r;
    tree[cur].mult = 1;
    if (l == r) {
        tree[cur].val = read();
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(cur), l, mid);
    build(rs(cur), mid + 1, r);
    push_up(cur);
}

void update(int cur, int l, int r, int op, int v)
{
    if (tree[cur].l == l and tree[cur].r == r) {
        if (op == 1) {
            tree[cur].val = tree[cur].val * v % mod;
            tree[cur].add = tree[cur].add * v % mod;
            tree[cur].mult = tree[cur].mult * v % mod;
        } else {
            tree[cur].val = (tree[cur].val + (r - l + 1) * v) % mod;
            tree[cur].add = (tree[cur].add + v) % mod;
        }
        return;
    }
    push_down(cur);
    int mid = (tree[cur].l + tree[cur].r) >> 1;
    if (r <= mid) {
        update(ls(cur), l, r, op, v);
    } else if (l > mid) {
        update(rs(cur), l, r, op, v);
    } else {
        update(ls(cur), l, mid, op, v);
        update(rs(cur), mid + 1, r, op, v);
    }
    push_up(cur);
}

ll query(int cur, int l, int r)
{
    if (tree[cur].l == l and tree[cur].r == r) {
        return tree[cur].val;
    }
    push_down(cur);
    int mid = (tree[cur].l + tree[cur].r) >> 1;
    if (r <= mid) {
        return query(ls(cur), l, r);
    }
    if (l > mid) {
        return query(rs(cur), l, r);
    }
    return (query(ls(cur), l, mid) + query(rs(cur), mid + 1, r)) % mod;
}

int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("input.txt", "r", stdin);
#endif
    int n = read(), m = read();
    mod = read();
    build(1, 1, n);
    while (m--) {
        int op = read(), x = read(), y = read();
        if (op == 3) {
            write(query(1, x, y), true);
        } else {
            update(1, x, y, op, read());
        }
    }
    return 0;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://doc.macrohard.cn/templates/ds/segment-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.