×

# Segment tree

 0 Problem link:-https://www.codechef.com/problems/QPALIN How to use segtree in such questions...I have done practice of some questions(basic) using segtree? here comes string. asked 01 Apr '17, 11:02 904●10 accept rate: 9%

 0 You can solve it by segment tree or BIT. Here's my solution using BIT > link text Solution We need to find number of odd characters in interval l to r. If it is less than 2 then answer will be YES else NO. So we need to maintain a frequency array for each alphabet in the range 1 to n. Answer each query in logn complexity which can be done using BIT/segment tree. answered 01 Apr '17, 12:26 922●13 accept rate: 11%
 1 I just looked at its editorial and found a very interesting optimization. We can solve it without creating hash tables or 26-length array in each node. We will use a very beautiful property of XOR operation, which is, XORing same number even number of times cancels out. For, e.g, 2 ^ 3 ^ 1 ^ 2 = 1 ^ 3 Thus only those terms gets XORed which appear odd number of times, we can use this to our advantage. Since we are using 26 character in our string, each character can be thought as integer whose only ith bit is set to 1 and i = ASCII(character) - 97. Thus we would be needing at most 26 bits, and thus normal "int" would suffice for our purpose. For merging two nodes, just XOR the numbers, and finally check the number of bits set to 1. If you are still confused, then look at this, almost same as the previous one. Solution answered 01 Apr '17, 18:30 187●2●13 accept rate: 0% 2 Neat! Similar approach is used here > http://codeforces.com/contest/570/problem/D (01 Apr '17, 21:23)
 0 If you are concerned just about how to handle string, then you can replace them with their ASCII number. Following observations are sufficient to solve this problem 1) if the string has even length it can be palindrome iff all the characters have even frequency of occurrence 2) if the string has odd length it can be palindrome iff exactly one character has odd frequency of occurrence BIT works faster than Segment-Tree, but not asymptotically. So if you already know BIT then you should see dushsingh1995 solution. Otherwise, here is one Segment-Tree based solution for you Solution EDIT : you can further reduce these observations to one pointed out by dushsingh1995 answered 01 Apr '17, 13:49 187●2●13 accept rate: 0%
 0 @ashwanigautam Ok...I will definitely try it out...thanks answered 01 Apr '17, 14:24 904●10 accept rate: 9%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,700

question asked: 01 Apr '17, 11:02

question was seen: 425 times

last updated: 01 Apr '17, 21:23