Some Code Template Just for Fun.
View the Project on GitHub Yuri3-xr/CP-library
#include "DataStructure/SegmentTree.hpp"
#pragma once #include "../Template/Template.hpp" template <typename Info> struct SegmentTree { int N; int size; std::vector<Info> seg; SegmentTree(int _N) { init(_N); } //[0,v.size) SegmentTree(const std::vector<Info> &v) { init(v.size()); for (int i = 0; i < (int)v.size(); i++) { seg[i + size] = v[i]; } build(); } void init(int _N) { N = _N; size = 1; while (size < N) size <<= 1; seg.assign(2 * size, Info()); } void set(int k, const Info &x) { seg[k + size] = x; } void build() { for (int k = size - 1; k > 0; k--) { seg[k] = seg[2 * k] + seg[2 * k + 1]; } } void update(int k, const Info &x) { k += size; seg[k] = x; while (k >>= 1) { seg[k] = seg[2 * k] + seg[2 * k + 1]; } } void add(int k, const Info &x) { k += size; seg[k] += x; while (k >>= 1) { seg[k] = seg[2 * k] + seg[2 * k + 1]; } } // query to [a, b) Info query(int a, int b) { Info L = Info(), R = Info(); for (a += size, b += size; a < b; a >>= 1, b >>= 1) { if (a & 1) L = L + seg[a++]; if (b & 1) R = seg[--b] + R; } return L + R; } Info &operator[](const int &k) { return seg[k + size]; } };
#line 2 "Template/Template.hpp" #include <bits/stdc++.h> using i64 = std::int64_t; #line 3 "DataStructure/SegmentTree.hpp" template <typename Info> struct SegmentTree { int N; int size; std::vector<Info> seg; SegmentTree(int _N) { init(_N); } //[0,v.size) SegmentTree(const std::vector<Info> &v) { init(v.size()); for (int i = 0; i < (int)v.size(); i++) { seg[i + size] = v[i]; } build(); } void init(int _N) { N = _N; size = 1; while (size < N) size <<= 1; seg.assign(2 * size, Info()); } void set(int k, const Info &x) { seg[k + size] = x; } void build() { for (int k = size - 1; k > 0; k--) { seg[k] = seg[2 * k] + seg[2 * k + 1]; } } void update(int k, const Info &x) { k += size; seg[k] = x; while (k >>= 1) { seg[k] = seg[2 * k] + seg[2 * k + 1]; } } void add(int k, const Info &x) { k += size; seg[k] += x; while (k >>= 1) { seg[k] = seg[2 * k] + seg[2 * k + 1]; } } // query to [a, b) Info query(int a, int b) { Info L = Info(), R = Info(); for (a += size, b += size; a < b; a >>= 1, b >>= 1) { if (a & 1) L = L + seg[a++]; if (b & 1) R = seg[--b] + R; } return L + R; } Info &operator[](const int &k) { return seg[k + size]; } };