Gss3 spoj Fenwick

#include <iostream>
#include <vector>
#include <numeric>
#include <random>
#include <cassert>
#include <chrono>
#include <tuple>

using namespace std;

// Fenwick Tree (Range Update/Range Query) - Provided in the prompt
#define LSB(x)((x) & -(x))
#define PARENT(x)(x + LSB(x))
#define LEFT_SIBLING(x) ((x) - LSB(x))

using namespace std;

FILE * fpbuf = stdin;

const int BUFSIZE = 6140;

int ibuf = 0, ibufsz = 0;

char buffer[BUFSIZE];

#define fillbuf() { ibufsz = fread(buffer, sizeof(char), BUFSIZE, fpbuf); ibuf = 0; }

inline int readint() {
    int no = 0;
    while (ibuf == ibufsz || buffer[ibuf] == '\n' || buffer[ibuf] == '\r' || buffer[ibuf] == ' ') {
        if (ibuf == ibufsz) {
            fillbuf();
            if (ibufsz == 0) break;
        } else ibuf++;
    }
    int sgn = 1;
    if (buffer[ibuf] == '-') {
        sgn *= -1;
        ++ibuf;
    }

    while (1) {
        if (ibuf == ibufsz) {
            fillbuf();
            if (ibufsz == 0) break;
        }
        char ch = buffer[ibuf++];
        if (ch == '\r' || ch == '\n' || ch == EOF || ch == ' ') break;
        no = (no << 3) + (no << 1) + ch - 48;
    }
    return no * sgn;
}

inline int readstr(char * d, bool spacebrk = true) {
    while (ibuf == ibufsz || buffer[ibuf] == '\n' || buffer[ibuf] == '\r' || buffer[ibuf] == ' ') {
        if (ibuf == ibufsz) {
            fillbuf();
            if (ibufsz == 0) return 0;
        } else ibuf++;
    }
    int i = 0;
    while (true) {
        if (ibuf == ibufsz) {
            fillbuf();
            if (ibufsz == 0) break;
        }
        char ch = buffer[ibuf++];
        if (ch == '\r' || ch == '\n' || ch == EOF || (spacebrk && ch == ' ')) break;
        d[i++] = ch;
    }
    d[i] = '\0';
    return i;
}

inline void fastwritestr(char * s) {
    while (*s) putchar(*s++);
}

char numbuf[20];

inline void fastwriteint(int no) {
    numbuf[0] = '0';
    int i = no == 0 ? 1 : 0;
    bool neg = no < 0;
    if (neg) no *= -1;
    while (no) {
        numbuf[i++] = no % 10 + 48;
        no /= 10;
    }
    if (neg) putchar('-');
    while (i > 0) putchar(numbuf[--i]);
}

#define LSB(x) ((x) & -(x))
#define foreach_fenwick_children(child, nd) \
    for (int sibling = LEFT_SIBLING(nd), child = (nd) - 1; child > sibling; child -= LSB(child))

const int MAXN = 50001;
const int LOGN = 16;

struct VALUE {
    int best_prefix;
    int best_suffix;
    int best;
    int sum;
};

VALUE point[MAXN];
VALUE tree[MAXN];
int n_fenwick;

VALUE combine_value(const VALUE &a, const VALUE &b) {
    int pref = max(a.best_prefix, a.sum + b.best_prefix);
    int suf  = max(b.best_suffix, b.sum + a.best_suffix);
    int sum  = a.sum + b.sum;

    int best = max(a.best, b.best);
    best = max(best, a.best_suffix + b.best_prefix);

    return {pref, suf, best, sum};
}

void combine(int nd) {
    if (nd > n_fenwick) return;
    tree[nd] = point[nd];
    foreach_fenwick_children(chld, nd) {
        tree[nd] = combine_value(tree[chld], tree[nd]);
    }
}

void update(int nd, int val) {
    point[nd]={ val, val, val, val };
    while (nd <= n_fenwick) {
        combine(nd);
        nd=PARENT(nd);
    }
}

VALUE range_query_fenwick(int l, int r) {
    VALUE ans;
    bool empty = true;

    while (l <= r) {
        int nr = LEFT_SIBLING(r);
        bool exceed = nr < l - 1;
const VALUE &segment = exceed ? point[r] : tree[r];
ans = empty ? segment : combine_value(segment, ans);
            r = exceed ? r-1 : nr;
        empty = false;
    }
    return ans;
}

int main() {
    int n;
    n = readint();
    n_fenwick = n;

    for (int i = 1; i <= n; ++i) {
        int v = readint();
        point[i] = {v, v, v, v};
        combine(i);
    }

    int q = readint();
    while (q--) {
        int t, a, b;
        t = readint();
        a = readint();
        b = readint();
        if (t == 0) {
            update(a, b);
            continue;
        }
        int res = range_query_fenwick(a, b).best;
        fastwriteint(res);
        putchar('\n');
    }

    return 0;
}