Language: C++

#include <cstddef>
#include <cstdint>
#include <functional>
#include <memory>
#include <utility>

template <class Monoid, template <class> class Allocator = std::allocator,
	class Index = std::size_t>
	class PersistentSegmentTree {
	public:
		using value_type = Monoid;
		using reference = value_type &;
		using const_reference = const value_type &;
		using size_type = Index;

	private:
		using F = std::function<value_type(const_reference)>;
		struct node_type {
			using pointer = std::shared_ptr<const node_type>;
			const value_type value;
			const pointer left, right;
			template <class L, class R>
			node_type(L &l, R &r)
				: value(l->value + r->value), left(std::forward<L>(l)),
				right(std::forward<R>(r)) {}
			node_type(const value_type &v) : value(v), left(), right() {}
			node_type(value_type &&v) : value(std::move(v)), left(), right() {}
			node_type(pointer &&p)
				: value(value_type()), left(p), right(std::move(p)) {}
			value_type range(size_type first, size_type last, size_type l,
				size_type r) const {
				if (r <= first || last <= l)
					return value_type();
				if (first <= l && r <= last)
					return value;
				return left->range(first, last, l, (l + r) >> 1) +
					right->range(first, last, (l + r) >> 1, r);
			}
			pointer update(size_type index, size_type height, const F &f) const {
				if (!~height)
					return std::allocate_shared<const node_type>(alc, f(value));
				if (index >> height & 1)
					return std::allocate_shared<const node_type>(
						alc, left, right->update(index, height - 1, f));
				else
					return std::allocate_shared<const node_type>(
						alc, left->update(index, height - 1, f), right);
			}
		};

	public:
		using allocator_type = Allocator<node_type>;
		using pointer = std::shared_ptr<const node_type>;

	private:
		size_type height_;
		pointer root_;
		static allocator_type alc;
		static size_type getheight(size_type size) {
			return size ? getheight(size >> 1) + 1 : 0;
		}
		static pointer build(size_type height) {
			if (!height)
				return std::allocate_shared<const node_type>(alc, value_type());
			return std::allocate_shared<const node_type>(alc, build(height - 1));
		}
		explicit PersistentSegmentTree(pointer &&root, size_type height)
			: height_(height), root_(std::move(root)) {}

	public:
		PersistentSegmentTree() : height_(0), root_() {}
		explicit PersistentSegmentTree(size_type size)
			: height_(size ? getheight(size - 1) : 0), root_(build(height_)) {}

		static void set_allocator(const allocator_type &x) { alc = x; }
		static void set_allocator(allocator_type &&x) { alc = std::move(x); }

		value_type range(size_type first, size_type last) const {
			return root_->range(first, last, 0, static_cast<size_type>(1) << height_);
		}

		PersistentSegmentTree update(size_type index, const F &f) const {
			return PersistentSegmentTree(root_->update(index, height_ - 1, f), height_);
		}
		PersistentSegmentTree update(size_type index, const value_type &data) const {
			return PersistentSegmentTree(
				root_->update(index, height_ - 1,
					[&data](const_reference v) { return data; }),
				height_);
		}
};
template <class Monoid, template <class> class Allocator, class Index>
typename PersistentSegmentTree<Monoid, Allocator, Index>::allocator_type
PersistentSegmentTree<Monoid, Allocator, Index>::alc = {};
#include<iostream>

int main() {
	int n, q;
	std::cin >> n >> q;
	PersistentSegmentTree<int> T(n);
	while (q--) {
		int c, x, y;
		std::cin >> c >> x >> y;
		if (c)
			std::cout << T.range(x - 1, y) << std::endl;
		else
			T = T.update(x - 1, [y](int t) { return t + y;});
	}
	return 0;
}


Compiler output:
In file included from /usr/include/x86_64-linux-gnu/c++/14/bits/c++allocator.h:33,
                 from /usr/include/c++/14/bits/allocator.h:46,
                 from /usr/include/c++/14/bits/alloc_traits.h:39,
                 from /usr/include/c++/14/ext/alloc_traits.h:34,
                 from /usr/include/c++/14/bits/hashtable_policy.h:39,
                 from /usr/include/c++/14/bits/hashtable.h:35,
                 from /usr/include/c++/14/bits/unordered_map.h:33,
                 from /usr/include/c++/14/unordered_map:41,
                 from /usr/include/c++/14/functional:63,
                 from a.cc:3:
/usr/include/c++/14/bits/new_allocator.h: In instantiation of 'void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = const PersistentSegmentTree<int>::node_type; _Args = {const std::shared_ptr<const PersistentSegmentTree<int>::node_type>&, std::shared_ptr<const PersistentSegmentTree<int>::node_type>}; _Tp = PersistentSegmentTree<int>::node_type]':
/usr/include/c++/14/bits/alloc_traits.h:575:17:   required from 'static void std::allocator_traits<std::allocator<_Tp1> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = const PersistentSegmentTree<int>::node_type; _Args = {const std::shared_ptr<const PersistentSegmentTree<int>::node_type>&, std::shared_ptr<const PersistentSegmentTree<int>::node_type>}; _Tp = PersistentSegmentTree<int>::node_type; allocator_type = std::allocator<PersistentSegmentTree<int>::node_type>]'
  575 |           __a.construct(__p, std::forward<_Args>(__args)...);
      |           ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/shared_ptr_base.h:607:39:   required from 'std::_Sp_counted_ptr_inplace<_Tp, _Alloc, _Lp>::_Sp_counted_ptr_inplace(_Alloc, _Args&& ...) [with _Args = {const std::shared_ptr<const PersistentSegmentTree<int>::node_type>&, std::shared_ptr<const PersistentSegmentTree<int>::node_type>}; _Tp = const PersistentSegmentTree<int>::node_type; _Alloc = std::allocator<PersistentSegmentTree<int>::node_type>; __gnu_cxx::_Lock_policy _Lp = __gnu_cxx::_S_atomic]'
  607 |           allocator_traits<_Alloc>::construct(__a, _M_ptr(),
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
  608 |               std::forward<_Args>(__args)...); // might throw
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
/usr/include/c++/14/bits/shared_ptr_base.h:969:16:   required from 'std::__shared_count<_Lp>::__shared_count(_Tp*&, std::_Sp_alloc_shared_tag<_Alloc>, _Args&& ...) [with _Tp = const PersistentSegmentTree<int>::node_type; _Alloc = std::allocator<PersistentSegmentTree<int>::node_type>; _Args = {const std::shared_ptr<const PersistentSegmentTree<int>::node_type>&, std::shared_ptr<const PersistentSegmentTree<int>::node_type>}; __gnu_cxx::_Lock_policy _Lp = __gnu_cxx::_S_atomic]'
  969 |           auto __pi = ::new (__mem)
      |                       ^~~~~~~~~~~~~
  970 |             _Sp_cp_type(__a._M_a, std::forward<_Args>(__args)...);
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/shared_ptr_base.h:1713:14:   required from 'std::__shared_ptr<_Tp, _Lp>::__shared_ptr(std::_Sp_alloc_shared_tag<_Tp>, _Args&& ...) [with _Alloc = std::allocator<PersistentSegmentTree<int>::node_type>; _Args = {const std::shared_ptr<const PersistentSegmentTree<int>::node_type>&, std::shared_ptr<const PersistentSegmentTree<int>::node_type>}; _Tp = const PersistentSegmentTree<int>::node_type; __gnu_cxx::_Lock_policy _Lp = __gnu_cxx::_S_atomic]'
 1713 |         : _M_ptr(), _M_refcount(_M_ptr, __tag, std::forward<_Args>(__args)...)
      |                     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/shared_ptr.h:463:59:   required from 'std::shared_ptr<_Tp>::shared_ptr(std::_Sp_alloc_shared_tag<_Tp>, _Args&& ...) [with _Alloc = std::allocator<PersistentSegmentTree<int>::node_type>; _Args = {const std::shared_ptr<const PersistentSegmentTree<int>::node_type>&, std::shared_ptr<const PersistentSegmentTree<int>::node_type>}; _Tp = const PersistentSegmentTree<int>::node_type]'
  463 |         : __shared_ptr<_Tp>(__tag, std::forward<_Args>(__args)...)
      |                                                                  ^
/usr/include/c++/14/bits/shared_ptr.h:990:14:   required from 'std::shared_ptr<typename std::enable_if<(! std::is_array<_Tp>::value), _Tp>::type> std::allocate_shared(const _Alloc&, _Args&& ...) [with _Tp = const PersistentSegmentTree<int>::node_type; _Alloc = allocator<PersistentSegmentTree<int>::node_type>; _Args = {const shared_ptr<const PersistentSegmentTree<int>::node_type>&, shared_ptr<const PersistentSegmentTree<int>::node_type>}; typename enable_if<(! is_array<_Tp>::value), _Tp>::type = const PersistentSegmentTree<int>::node_type]'
  990 |       return shared_ptr<_Tp>(_Sp_alloc_shared_tag<_Alloc>{__a},
      |              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  991 |                              std::forward<_Args>(__args)...);
      |                              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:43:50:   required from 'PersistentSegmentTree<Monoid, Allocator, Index>::node_type::pointer PersistentSegmentTree<Monoid, Allocator, Index>::node_type::update(PersistentSegmentTree<Monoid, Allocator, Index>::size_type, PersistentSegmentTree<Monoid, Allocator, Index>::size_type, const PersistentSegmentTree<Monoid, Allocator, Index>::F&) const [with Monoid = int; Allocator = std::allocator; Index = long unsigned int; pointer = std::shared_ptr<const PersistentSegmentTree<int>::node_type>; PersistentSegmentTree<Monoid, Allocator, Index>::size_type = long unsigned int; PersistentSegmentTree<Monoid, Allocator, Index>::F = std::function<int(const int&)>]'
   43 |                                         return std::allocate_shared<const node_type>(
      |                                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
   44 |                                                 alc, left, right->update(index, height - 1, f));
      |                                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:83:46:   required from 'PersistentSegmentTree<Monoid, Allocator, Index> PersistentSegmentTree<Monoid, Allocator, Index>::update(size_type, const F&) const [with Monoid = int; Allocator = std::allocator; Index = long unsigned int; size_type = long unsigned int; F = std::function<int(const int&)>]'
   83 |                         return PersistentSegmentTree(root_->update(index, height_ - 1, f), height_);
      |                                                      ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
a.cc:107:16:   required from here
  107 |                         T = T.update(x - 1, [y](int t) { return t + y;});
      |                             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/new_allocator.h:191:11: error: cannot bind non-const lvalue reference of type 'std::shared_ptr<const PersistentSegmentTree<int>::node_type>&' to an rvalue of type 'std::shared_ptr<const PersistentSegmentTree<int>::node_type>'
  191 |         { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:23:44: note:   initializing argument 2 of 'PersistentSegmentTree<Monoid, Allocator, Index>::node_type::node_type(L&, R&) [with L = const std::shared_ptr<const PersistentSegmentTree<int>::node_type>; R = std::shared_ptr<const PersistentSegmentTree<int>::node_type>; Monoid = int; Allocator = std::allocator; Index = long unsigned int]'
   23 |                         node_type(L &l, R &r)
      |                                         ~~~^
/usr/include/c++/14/bits/new_allocator.h: In instantiation of 'void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = const PersistentSegmentTree<int>::node_type; _Args = {std::shared_ptr<const PersistentSegmentTree<int>::node_type>, const std::shared_ptr<const PersistentSegmentTree<int>::node_type>&}; _Tp = PersistentSegmentTree<int>::node_type]':
/usr/include/c++/14/bits/alloc_traits.h:575:17:   required from 'static void std::allocator_traits<std::allocator<_Tp1> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = const PersistentSegmentTree<int>::node_type; _Args = {std::shared_ptr<const PersistentSegmentTree<int>::node_type>, const std::shared_ptr<const PersistentSegmentTree<int>::node_type>&}; _Tp = PersistentSegmentTree<int>::node_type; allocator_type = std::allocator<PersistentSegmentTree<int>::node_type>]'
  575 |           __a.construct(__p, std::forward<_Args>(__args)...);
      |           ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/shared_ptr_base.h:607:39:   required from 'std::_Sp_counted_ptr_inplace<_Tp, _Alloc, _Lp>::_Sp_counted_ptr_inplace(_Alloc, _Args&& ...) [with _Args = {std::shared_ptr<const PersistentSegmentTree<int>::node_type>, const std::shared_ptr<const PersistentSegmentTree<int>::node_type>&}; _Tp = const PersistentSegmentTree<int>::node_type; _Alloc = std::allocator<PersistentSegmentTree<int>::node_type>; __gnu_cxx::_Lock_policy _Lp = __gnu_cxx::_S_atomic]'
  607 |           allocator_traits<_Alloc>::construct(__a, _M_ptr(),
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
  608 |               std::forward<_Args>(__args)...); // might throw
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
/usr/include/c++/14/bits/shared_ptr_base.h:969:16:   required from 'std::__shared_count<_Lp>::__shared_count(_Tp*&, std::_Sp_alloc_shared_tag<_Alloc>, _Args&& ...) [with _Tp = const PersistentSegmentTree<int>::node_type; _Alloc = std::allocator<PersistentSegmentTree<int>::node_type>; _Args = {std::shared_ptr<const PersistentSegmentTree<int>::node_type>, const std::shared_ptr<const PersistentSegmentTree<int>::node_type>&}; __gnu_cxx::_Lock_policy _Lp = __gnu_cxx::_S_atomic]'
  969 |           auto __pi = ::new (__mem)
      |                       ^~~~~~~~~~~~~
  970 |             _Sp_cp_type(__a._M_a, std::forward<_Args>(__args)...);
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/shared_ptr_base.h:1713:14:   required from 'std::__shar