セグメントツリー(C言語貼り付け用)

すぐに見つからなかったので自分用

以下をmainの上あたりに貼り付け

typedef struct str_segtree
{
    int (*op)(int, int);
    void (*change)(int, int);
    int (*query)(int, int);
    void (*scan)(void);
    void (*check)(void);
    int *data;
} segtree_t;

void segtree_scan(void);
void segtree_change(int a, int b);
int segtree_query(int a, int b);
int segtree_query_internal(int a, int b, int k, int l, int r);
void segtree_check(void);
static int seg_n;
static int *seg_dat;
static int seg_e;
segtree_t *segtree_;

segtree_t *seg_init(int n, void *func, int e)
{
    int i;
    seg_n = 1;
    seg_e = e;

    while (seg_n < n)
        seg_n *= 2;
    segtree_ = malloc(sizeof(segtree_t));
    seg_dat = malloc(sizeof(int) * (2 * seg_n - 1));
    for (i = seg_n - 2 + n; i < (2 * seg_n - 1); i++)
    {
        seg_dat[i] = e;
    }
    segtree_->change = segtree_change;
    segtree_->op = (int (*)(int, int))func;
    segtree_->scan = segtree_scan;
    segtree_->check = segtree_check;
    segtree_->query = segtree_query;
    segtree_->data = &seg_dat[seg_n - 1];
    return segtree_;
}

void segtree_scan(void)
{
    int i;
    for (i = seg_n - 2; i >= 0; i--)
    {
        seg_dat[i] = segtree_->op(seg_dat[2 * i + 1], seg_dat[2 * i + 2]);
        // printf("%d -> %d ^ %d\n", i, seg_dat[2 * i + 1], seg_dat[2 * i + 2]);
    }
}

void segtree_change(int a, int b)
{
    a += (seg_n - 1);
    seg_dat[a] = b;
    while (a > 0)
    {
        a = (a - 1) / 2;
        seg_dat[a] = segtree_->op(seg_dat[2 * a + 1], seg_dat[2 * a + 2]);
    }
}

int segtree_query(int a, int b)
{
    return segtree_query_internal(a, b, 0, 0, seg_n);
}

int segtree_query_internal(int a, int b, int k, int l, int r)
{
    int vl, vr;
    if (r <= a || b <= l)
        return seg_e;
    else if (a <= l && r <= b)
        return seg_dat[k];
    else
    {
        vl = segtree_query_internal(a, b, 2 * k + 1, l, (l + r) / 2);
        vr = segtree_query_internal(a, b, 2 * k + 2, (l + r) / 2, r);
        return segtree_->op(vl, vr);
    }
}
void segtree_check(void)
{
    int i;
    printf("check:\t");
    for (i = 0; i < seg_n * 2 - 1; i++)
    {
        printf("%d ", seg_dat[i]);
    }
    printf("\n");
}

使い方

https://atcoder.jp/contests/abc185/tasks/abc185_f
の場合

int func(int a, int b)
{
    return a ^ b;
}

int main(void)
{
    int n, q;
    int a;
    int *t, *x, *y;
    segtree_t *seg;
    int i;

    scanf("%d %d", &n, &q);
    seg = seg_init(n, func, 0);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &a);
        seg->data[i] = a;
    }
    // seg->check();

    seg->scan();

    // seg->check();

    t = malloc(sizeof(int) * q);
    x = malloc(sizeof(int) * q);
    y = malloc(sizeof(int) * q);
    for (i = 0; i < q; i++)
    {
        scanf("%d %d %d", &t[i], &x[i], &y[i]);
    }

    for (i = 0; i < q; i++)
    {
        if (t[i] == 1)
        {
            seg->change(x[i] - 1, seg->data[x[i] - 1] ^ y[i]);
        }
        else
        {
            printf("%d\n", seg->query(x[i] - 1, y[i]));
        }
    }

    return 0;
}

右端は含まないindexなので -1しない（t[i] != 1のとき）。

---

参考