RetroSearch Browse

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d2/d45/segtree_8cpp_source.html below:

TheAlgorithms/C++: range_queries/segtree.cpp Source File

38void ConsTree

(

const

std::vector<int64_t> &arr, std::vector<int64_t> *segtree,

39

uint64_t low, uint64_t high, uint64_t pos) {

41

(*segtree)[pos] = arr[low];

45

uint64_t mid = (low + high) / 2;

46 ConsTree

(arr, segtree, low, mid, 2 * pos + 1);

47 ConsTree

(arr, segtree, mid + 1, high, 2 * pos + 2);

48

(*segtree)[pos] = (*segtree)[2 * pos + 1] + (*segtree)[2 * pos + 2];

63

int64_t

query

(std::vector<int64_t> *segtree, std::vector<int64_t> *lazy,

64

uint64_t qlow, uint64_t qhigh, uint64_t low, uint64_t high,

66 if

(low > high || qlow > high || low > qhigh) {

70 if

((*lazy)[pos] != 0) {

71

(*segtree)[pos] += (*lazy)[pos] * (high - low + 1);

74

(*lazy)[2 * pos + 1] += (*lazy)[pos];

75

(*lazy)[2 * pos + 2] += (*lazy)[pos];

80 if

(qlow <= low && qhigh >= high) {

81 return

(*segtree)[pos];

84

uint64_t mid = (low + high) / 2;

86 return query

(segtree, lazy, qlow, qhigh, low, mid, 2 * pos + 1) +

87 query

(segtree, lazy, qlow, qhigh, mid + 1, high, 2 * pos + 2);

103void update

(std::vector<int64_t> *segtree, std::vector<int64_t> *lazy,

104

int64_t start, int64_t end, int64_t delta, uint64_t low,

105

uint64_t high, uint64_t pos) {

110 if

((*lazy)[pos] != 0) {

111

(*segtree)[pos] += (*lazy)[pos] * (high - low + 1);

114

(*lazy)[2 * pos + 1] += (*lazy)[pos];

115

(*lazy)[2 * pos + 2] += (*lazy)[pos];

120 if

(start > high || end < low) {

124 if

(start <= low && end >= high) {

125

(*segtree)[pos] += delta * (high - low + 1);

128

(*lazy)[2 * pos + 1] += delta;

129

(*lazy)[2 * pos + 2] += delta;

135

uint64_t mid = (low + high) / 2;

137 update

(segtree, lazy, start, end, delta, low, mid, 2 * pos + 1);

138 update

(segtree, lazy, start, end, delta, mid + 1, high, 2 * pos + 2);

139

(*segtree)[pos] = (*segtree)[2 * pos + 1] + (*segtree)[2 * pos + 2];

148 auto

max =

static_cast<

int64_t

>

(2 * pow(2, ceil(log2(7))) - 1);

151

std::vector<int64_t> arr{1, 2, 3, 4, 5, 6, 7}, lazy(max), segtree(max);

152 ConsTree

(arr, &segtree, 0, 7 - 1, 0);

154

assert(

query

(&segtree, &lazy, 1, 5, 0, 7 - 1, 0) == 2 + 3 + 4 + 5 + 6);

156 update

(&segtree, &lazy, 2, 4, 1, 0, 7 - 1, 0);

157

assert(

query

(&segtree, &lazy, 1, 5, 0, 7 - 1, 0) == 2 + 4 + 5 + 6 + 6);

159 update

(&segtree, &lazy, 0, 6, -2, 0, 7 - 1, 0);

160

assert(

query

(&segtree, &lazy, 0, 4, 0, 7 - 1, 0) == -1 + 0 + 2 + 3 + 4);

171

std::cout <<

"Enter number of elements: "

;

176 auto

max =

static_cast<

uint64_t

>

(2 * pow(2, ceil(log2(n))) - 1);

177

std::vector<int64_t> arr(n), lazy(max), segtree(max);

180

std::cout <<

"\nDo you wish to enter each number?:\n" 182 "0: No (default initialize them to 0)\n"

;

186

std::cout <<

"Enter "

<< n <<

" numbers:\n"

;

187 for

(

int

i = 1; i <= n; i++) {

188

std::cout << i <<

": "

;

193 ConsTree

(arr, &segtree, 0, n - 1, 0);

196

std::cout <<

"\nMake your choice:\n" 197 "1: Range update (input)\n" 198 "2: Range query (output)\n" 203

std::cout <<

"Enter 1-indexed lower bound, upper bound & value:\n"

;

205

uint64_t p = 1, q = 1, v = 0;

206

std::cin >> p >> q >> v;

207 update

(&segtree, &lazy, p - 1, q - 1, v, 0, n - 1, 0);

208

}

else if

(choice == 2) {

209

std::cout <<

"Enter 1-indexed lower bound & upper bound:\n"

;

211

uint64_t p = 1, q = 1;

213

std::cout <<

query

(&segtree, &lazy, p - 1, q - 1, 0, n - 1, 0);

216

}

while

(choice > 0);

int64_t query(std::vector< int64_t > *segtree, std::vector< int64_t > *lazy, uint64_t qlow, uint64_t qhigh, uint64_t low, uint64_t high, uint64_t pos)

Returns the sum of all elements in a range.

static void test()

Self-test implementation.

void update(std::vector< int64_t > *segtree, std::vector< int64_t > *lazy, int64_t start, int64_t end, int64_t delta, uint64_t low, uint64_t high, uint64_t pos)

Updates a range of the segment tree.

int main()

Main function.

void ConsTree(const std::vector< int64_t > &arr, std::vector< int64_t > *segtree, uint64_t low, uint64_t high, uint64_t pos)

for std::vector

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4