Или с иррационалтными коэффициентами, там вероятность попадания в вершину настолько низкая, что для практики можно не париться

Для меня работает корректно, хотя на  всех случаях не тестировал, делал по этой работе
https://www.mdpi.com/2073-8994/10/10/477/pdf
(Optimal Reliable Point-in-Polygon Test and
Differential Coding Boolean Operations on Polygons)

Для теста в фигуре просто ввожу все контурные точки

Привет всем, а как найти в дереве Фенвика минимальный индекс, в котором префикс сумма равна заданному значению за O(logN)??

int l = 0, r = n;
while(l < r) {
   int midd = l + (r-l)/2;
   if (get_sum(BIT, midd+1) < given_sum)
       l = midd+1;
   else
       r = midd;
}
// res => midd + 1
Сейчас нахожу за O(log^2(N)), но наибольший и любой из индексов можно найти за O(logN), поэтому предполагаю, что и наименьший можно.

Обычное дерево Фенвика на массиве BIT(n+1, 0);
   void update(vector<int> &BIT, int idx, int delta){
       for(int i = idx; i < BIT.size(); i +=(i&-i))
           BIT[i] += delta;
   }
   int get_sum(vector<int>& BIT, int idx){
       int sum = 0;
       for(int i = idx; i > 0; i-=(i&-i))
           sum += BIT[i];
       return sum;
   }

Хм, обычный спуск по фенвику разве не должен работать?

хм... Как?
Вот пример обычного спуска из топкодера, но он же найдёт любой из индексов, а не наименьший?


int idx = 0; // this variable will be the output
while (bitMask != 0) {
   int tIdx = idx + bitMask;
   bitMask >>= 1;
   if (tIdx > MaxIdx)
     continue;
   if (cumFre == tree[tIdx])
     return tIdx;
   else if (cumFre > tree[tIdx]) {
     idx = tIdx;
     cumFre -= tree[tIdx];
   }
 }

числа неотрицательные, я так понимаю?

++

1 или 0 храняться

видимо нужно два прохода - вторым найти наименьший индекс, начиная с любого

Не совсем понял про второй проход.
За первый проход мы найдём любой индекс, в котором префикс сумма равна переданному значению, а на втором проходе, что искать?

на самом деле не надо двух проходов

если тут убрать cumFre == tree[tIdx] и поменять во втором условии > на >=, то оно должно находить максимальный индекс, сумма на котором меньше нужного

значит следующий - то что нужно

Ок, сейчас попробую осмыслить, спасибо

Если так сделать, то будет находить наибольший индекс с заданной суммой, а не наибольший индекс, сумма на котором меньше заданной...

А как в два прохода, не подскажите?

Может поддерживать фенвик с другой стороны просто?

убрать иф с == , поменять/не поменять > на >=, прибавить 1/0/-1 к результату, в каком то сочетании будет правильно

в каком именно - надо думать