// Copyright 2019 Nedelcu Horia ([email protected])
#ifndef SEGMENT_TREE_H_
#define SEGMENT_TREE_H_
#include <vector>
#include <algorithm>
template <typename Tinfo>
class DefaulCombiner {
public:
Tinfo operator()(Tinfo const &lsh, Tinfo const &rsh) {
return lsh + rsh;//std::max(lsh, rsh);
}
};
template <typename Tinfo, typename Combiner = DefaulCombiner<Tinfo> >
class SegmentTree {
private:
public:
int size_;
std::vector<Tinfo> tree_;
Combiner combine_;
public:
// Default Constructor
SegmentTree();
// Constructor
SegmentTree(std::vector<Tinfo> array);
// Destructor
~SegmentTree();
/*
* Build a segment tree from array.
*
* @param array // given array to build.
*/
void build(std::vector<Tinfo> array);
/**
* Update value of element from position p.
*
* @param p // Set value at position p.
*/
void update(int p, int value);
/**
* Get an aggregate on interval [l, r).
*
* @param l, r // left and right bounds of the interval.
* @return an aggregate on interval [l, r).
*/
Tinfo query(int l, int r);
/*
* Get size of array used.
*
* @return size of array used.
*/
int getSize();
};
template <typename Tinfo, typename Combiner>
SegmentTree<Tinfo, Combiner>::SegmentTree(): size_(0) {}
template <typename Tinfo, typename Combiner>
SegmentTree<Tinfo, Combiner>::SegmentTree(std::vector<Tinfo> array): size_(array.size()), tree_(2 * array.size()) {
for (int i = 0; i < size_; ++i) {
tree_[size_ + i] = array[i];
}
for (int i = size_ - 1; i > 0; --i) {
tree_[i] = combine_(tree_[i << 1], tree_[ i<< 1 | 1]);
}
}
template <typename Tinfo, typename Combiner>
SegmentTree<Tinfo, Combiner>::~SegmentTree() {}
template <typename Tinfo, typename Combiner>
void SegmentTree<Tinfo, Combiner>::build(std::vector<Tinfo> array) {
size_ = array.size();
tree_.resize(2 * size_);
for (int i = 0; i < size_; ++i) {
tree_[size_ + i] = array[i];
}
for (int i = size_ - 1; i > 0; --i) {
tree_[i] = combine_(tree_[i << 1], tree_[ i<< 1 | 1]);
}
}
template <typename Tinfo, typename Combiner>
void SegmentTree<Tinfo, Combiner>::update(int p, int value) {
for (tree_[p += size_] = value, p >>= 1; p > 1; p >>= 1) {
tree_[p] = combine_(tree_[p << 1], tree_[p << 1 | 1]);
}
}
template <typename Tinfo, typename Combiner>
Tinfo SegmentTree<Tinfo, Combiner>::query(int l, int r) {
bool usedl = false, usedr = false;
Tinfo retl, retr;
for (l += size_, r += size_; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
if (usedl) {
retl = combine_(retl, tree_[l++]);
} else {
retl = tree_[l++];
usedl = true;
}
}
if (r & 1) {
if (usedr) {
retr = combine_(tree_[--r], retr);
} else {
retr = tree_[--r];
usedr = true;
}
}
}
if (usedl && usedr) {
return combine_(retl, retr);
} else {
return (usedl)? retl: retr;
}
}
template <typename Tinfo, typename Combiner>
int SegmentTree<Tinfo, Combiner>::getSize() {
return size_;
}
#endif // SEGMENT_TREE_H_
#include <bits/stdc++.h>
using namespace std;
const int kBuffSize = 655536;
char outBuff[kBuffSize];
int outPtr;
#define fastcall __attribute__((optimize("-O3")))
#define inline __inline__ __attribute__((always_inline))
inline fastcall char getChar() {
static char buff[kBuffSize];
static int pos = kBuffSize;
if (pos == kBuffSize) {
fread(buff, 1, kBuffSize, stdin);
pos = 0;
}
return buff[pos++];
}
inline fastcall int readInt() {
int q = 0;
char c;
do {
c = getChar();
} while (!isdigit(c));
do {
q = (q << 1) + (q << 3) + (c - '0');
c = getChar();
} while (isdigit(c));
return q;
}
inline fastcall void putChar(const char &C) {
outBuff[outPtr++] = C;
if (outPtr == kBuffSize) {
fwrite(outBuff, 1, kBuffSize, stdout);
outPtr = 0;
}
}
inline fastcall void writeInt(int X) {
char digs[10];
int n = 0, q;
do {
q = X / 10;
digs[n++] = X - (q << 1) - (q << 3) + '0';
X = q;
} while (X);
while (n--) {
putChar(digs[n]);
}
putChar('\n');
}
template <typename Tinfo>
class myCombiner {
public:
Tinfo operator()(Tinfo const &lsh, Tinfo const &rsh) {
return std::max(lsh, rsh);
}
};
int main() {
freopen("arbint.in", "r", stdin);
freopen("arbint.out", "w", stdout);
int N, M, t, a, b;
SegmentTree<int, myCombiner<int> > tree;
N = readInt();
M = readInt();
std::vector<int> v(N);
for (int i = 0; i < N; ++i) {
v[i] = readInt();
}
tree.build(v);
for (int i = 0; i < M; ++i) {
t = readInt();
a = readInt();
b = readInt();
if (t != 0) {
tree.update(a - 1, b);
} else {
writeInt(tree.query(a - 1, b));
}
}
fclose(stdin);
fwrite(outBuff, 1, outPtr, stdout);
fclose(stdout);
return 0;
}