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

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d5/d58/persistent__seg__tree__lazy__prop_8cpp.html below:

TheAlgorithms/C++: range_queries/persistent_seg_tree_lazy_prop.cpp File Reference

Test implementations.

269 {

270 std::vector<int64_t> arr = {-5, 2, 3, 11, -2, 7, 0, 1};

272 std::cout << "Elements before any updates are {";

273 for (uint32_t i = 0; i < arr.size(); ++i) {

274 std::cout << arr[i];

275 if (i != arr.size() - 1) {

276 std::cout << ",";

277 }

278 }

279 std::cout << "}\n";

281 arr);

282 std::cout << "Querying range sum on version 0 from index 2 to 4 = 3+11-2 = "

<< tree.

(2, 4, 0) <<

;

284 std::cout

285 << "Subtract 7 from all elements from index 1 to index 5 inclusive\n";

287 std::cout << "Elements of the segment tree whose version = 1 (after 1 "

288 "update) are {";

289 for (uint32_t i = 0; i < arr.size(); ++i) {

std::cout << tree.

(i, i, 1);

291 if (i != arr.size() - 1) {

292 std::cout << ",";

293 }

294 }

295 std::cout << "}\n";

296 std::cout << "Add 10 to all elements from index 0 to index 7 inclusive\n";

298 std::cout << "Elements of the segment tree whose version = 2 (after 2 "

299 "updates) are {";

300 for (uint32_t i = 0; i < arr.size(); ++i) {

std::cout << tree.

(i, i, 2);

302 if (i != arr.size() - 1) {

303 std::cout << ",";

304 }

305 }

306 std::cout << "}\n";

std::cout <<

<< tree.

()

308 << '\n';

309 std::cout << "Querying range sum on version 0 from index 3 to 5 = 11-2+7 = "

<< tree.

(3, 5, 0) <<

;

311 std::cout << "Querying range sum on version 1 from index 3 to 5 = 4-9+0 = "

<< tree.

(3, 5, 1) <<

;

313}

Range query here is range sum, but the code can be modified to make different queries like range max ...

uint32_t size()

Getting the number of versions after updates so far which is equal to the size of the pointers vector...

std::shared_ptr< Node > update(const uint32_t &i, const uint32_t &j, const uint32_t &l, const uint32_t &r, const int64_t &value, std::shared_ptr< Node > const &curr)

Doing range update, checking at every node if it has some value to be propagated. All nodes affected ...

std::shared_ptr< Node > construct(const uint32_t &i, const uint32_t &j)

Constructing the segment tree with the early passed vector. Every call creates a node to hold the sum...

int64_t query(const uint32_t &i, const uint32_t &j, const uint32_t &l, const uint32_t &r, std::shared_ptr< Node > const &curr)

Querying the range from index l to index r, checking at every node if it has some value to be propaga...

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