ouuan's blog

By ouuan, history, 5 years ago, In English

Are you bored of writing duplicate codes when solving segment tree problems?

Did you find that segment trees have very little difference from each other?

Do you want a template, which allows you to code only the key parts, the parts different from other segment trees?

Then this template may help.

An example of segment add & multiply, segment query for sum modulo p:

codes

For more information (how to use it), please read README.md on Github.

  • Vote: I like it
  • +86
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +44 Vote: I do not like it

Protip: #define and global-level using shouldn't appear in headers. It restricts users of your code more than necessary. Defines can be completely replaced by inline functions or constexpr variables.

You're also doing things like duplicating initValues into the class, even though you only use it once.

The functions you pass as arguments can be template arguments.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks for reminding me. I'm not good at programming except CP, so there may be lots of mistakes.

    However, I used #undef at the end, and I think it may not restrict the users, am I right?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Okay, I didn't notice the undef, which is better — it's not perfect since it would undef identically named macros in earlier includes if they're used later in the code. Define/ifdef are good for things like choosing pieces of code based on compatibility (e.g. system-specific constants) or specific purpose if one source can be used for several programs.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        OK, I got it. And the issues mentioned by you are fixed now.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Just noticed that "duplicating initValues" means "duplicating init function". I used to let it be a public function, and then realized it's useless and make it private.

»
5 years ago, # |
  Vote: I like it -26 Vote: I do not like it

cool